QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#364052 | #8049. Equal Sums | ucup-team2219# | RE | 0ms | 0kb | C++14 | 2.0kb | 2024-03-24 10:58:22 | 2024-03-24 10:58:26 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[505][2],b[505][2];
int dp[2][505][1005],sum[2][505][1005],nw=0;
const int mod=998244353;
int M(int x)
{
if(x>=mod)return x-mod;
if(x<0)return x+mod;
return x;
}
int ask(int u,int v,int l,int r)
{
if(l>r)return 0;
assert(l>=1&&r<=1001);
return sum[u][v][r]-sum[u][v][l-1];
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i][0],&a[i][1]);
for(int i=1;i<=m;i++)scanf("%d%d",&b[i][0],&b[i][1]);
nw=0;
//dp[0][0].resize(1005,0);
//sum[0][0].resize(1005,0);
dp[0][0][501]=1;
for(int i=1;i<=1002;i++)sum[0][0][i]=M(sum[0][0][i-1]+dp[0][0][i]);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
if(i==0&&j==0)continue;
for(int k=1;k<=1001;k++)
{
dp[nw][j][k]=sum[nw][j][k]=0;
if(j>0)
{
int ly=501,ry=1001;
ly=max(501,k+b[j][0]);
ry=min(1001,k+b[j][1]);
//if(i==1&&j==1&&k==501)printf("#%d %d\n",ly,ry);
dp[nw][j][k]=M(dp[nw][j][k]+M(ask(nw,j-1,ly,ry)));
//if(k>=497&&k<=505)printf("#%d %d:%d %d %d %d\n",ly,ry,i,j,k-501,dp[nw][j][k]);
//if(i==1&&j==1&&k==501)printf("#%d\n",dp[i][j][k]);
}
if(i>0)
{
int ly=1,ry=501;
ly=max(1,k-a[i][1]);
ry=min(501,k-a[i][0]);
dp[nw][j][k]=M(dp[nw][j][k]+M(ask(!nw,j,ly,ry)));
// if(i==1&&j==0&&k>=497&&k<=505&&k==502)printf("%d %d %d:%d %d %d %d\n",nw,ly,ry,i,j,k-501,dp[nw][j][k]);
//if(i==1&&j==1&&k==501)printf("#%d\n",dp[i][j][k]);
if(j>0)
{
ly=max(501-b[j][1],k-a[i][1]);
ry=min(501-b[j][0],k-a[i][0]);
dp[nw][j][k]=M(1ll*dp[nw][j][k]-1ll*dp[!nw][j-1][501]*max(0ll,1ll*(ry-ly+1))%mod);
}
}
}
if(i>0&&j>0)
{
printf("%d",dp[nw][j][501]);
if(j==m)printf("\n");
else printf(" ");
}
for(int k=1;k<=1001;k++)sum[nw][j][k]=M(sum[nw][j][k-1]+dp[nw][j][k]);
//if(i>=2)vector<int>().swap(dp[i-2][j]),vector<int>().swap(sum[i-2][j]);
}
nw=!nw;
}
return 0;
}
詳細信息
Test #1:
score: 0
Dangerous Syscalls
input:
2 3 1 2 2 3 1 4 2 2 1 3