CCPC2024I 找行李

TLE on #11, O(n^3)DP写法，思路同官方题解

代码：

#include<bits/stdc++.h>
#define PII pair<int,int>
#define DB double
#define LL long long
#define int long long
//#define int __int128
//const int mod=1e9+7;
const int mod=998244353;
const LL inf=0x3f3f3f3f,INF=1e16;
namespace FastIO{
	inline int read(int mod){
		int x=0,f=1;char ch=getchar();
		if(mod==0){while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}}
		else{while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x*10%mod+ch-48)%mod;ch=getchar();}}
		return x*f;}
	inline char cread(){char x;while(x==0||x==' '||x=='\n'||x=='\r')x=getchar();return x;}
	inline void write(int x){if(x<0)putchar('-'),x=-x;if(x==0)return;write(x/10),putchar(x%10+'0');}
}
using namespace FastIO;
using namespace std;
int a[505],b[505];
int f[505][505],g[505];
signed main(){
	int n=read(0),m=read(0),ans=0;
	for(int i=1;i<=n;++i)a[i]=read(0);
	for(int i=1;i<=m;++i)b[i]=read(0);
	sort(a+1,a+1+n),sort(b+1,b+1+m);
	for(int k=0;k<=500;++k){
		for(int i=0;i<=m;++i)
			for(int j=0;j<=n;++j)
				f[i][j]=0;
		f[0][0]=1;
		for(int i=1;i<=m;++i){
			int sum=0;
			for(int j=1;j<=n;++j)
				if(b[i]-a[j]>=k)++sum;
			for(int j=0;j<=min(sum,n);++j){
				f[i][j]=f[i-1][j];
				if(j>0)f[i][j]=(f[i][j]+f[i-1][j-1]*(sum-(j-1))%mod)%mod;
			}
		}
		for(int j=0;j<=n;++j)g[k]=(g[k]+f[m][j])%mod;
	}
	for(int k=0;k<=499;++k)
		ans=(ans+(g[k]-g[k+1])*k%mod)%mod;
	printf("%lld\n",ans);
	return 0;
}