QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584734 | #8049. Equal Sums | Jessica2333 | WA | 1892ms | 11604kb | C++14 | 1.4kb | 2024-09-23 16:26:50 | 2024-09-23 16:26:50 |
Judging History
answer
#include<iostream>
#include<cstring>
#define int long long
using namespace std;
const int MOD=998244353;
int N,M,L[2][508],R[2][508];
int f[508][1008],g[508][1008],h[1008];
const int O=500;
signed main()
{
// bool flag=0;
cin>>N>>M;
for(int i=1;i<=N;i++) cin>>L[0][i]>>R[0][i];
for(int i=1;i<=M;i++) cin>>L[1][i]>>R[1][i];
g[0][O]=1;g[0][O+1]=-1;
for(int i=0;i<=N;i++)
{
for(int j=0;j<=M;j++)
{
f[j][0]=g[j][0];g[j][0]=0;
for(int k=1;k<=O+500;k++) (g[j][k]+=g[j][k-1])%=MOD,f[j][k]=g[j][k];
for(int k=0;k<=O+500;k++) g[j][k]=0;
}
for(int j=0;j<=M;j++)
{
for(int k=0;k<=O+500;k++)
{
if(k) (h[k]+=h[k-1])%MOD;
(f[j][k]+=h[k])%MOD;
}
memset(h,0,sizeof(h));
for(int k=0;k<=O+500;k++)
{
// if(f[j][k]) flag=1;else flag=0;
// if(flag) cout<<"f "<<i<<" "<<j<<" "<<k-O<<"="<<f[j][k]<<"\n";
if(k<=O)
{
// if(flag) cout<<k+L[0][i+1]-O<<" "<<k+R[0][i+1]+1-O<<"*\n";
(g[j][min(k+L[0][i+1],O+501)]+=f[j][k])%=MOD,(g[j][min(k+R[0][i+1]+1,O+501)]-=f[j][k])%=MOD;
}
else
{
// if(flag) cout<<k-R[1][j+1]-O<<" "<<k-L[1][j+1]+1-O<<"!\n";
(h[max(k-R[1][j+1],0ll)]+=f[j][k])%=MOD,(h[max(k-L[1][j+1]+1,0ll)]-=f[j][k])%MOD;
// (f[j+1][max(k-R[1][j+1],0ll)]+=f[j][k])%=MOD,(f[j+1][max(k-L[1][j+1]+1,0ll)]-=f[j][k])%MOD;
}
}
if(i>0&&j>0) cout<<(f[j][O]+MOD)%MOD<<" ";
}
if(i) cout<<"\n";
}
return 0;
}
//白鸟惊飞久不栖
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5740kb
input:
2 3 1 2 2 3 1 4 2 2 1 3
output:
2 0 0 3 4 4
result:
ok 6 numbers
Test #2:
score: -100
Wrong Answer
time: 1892ms
memory: 11604kb
input:
500 500 19 458 1 480 7 485 50 461 12 476 15 461 48 466 40 453 46 467 9 458 27 478 26 472 46 459 29 490 6 500 17 487 48 484 28 472 28 459 25 480 4 491 29 481 36 460 2 491 44 499 22 473 20 458 4 483 27 471 2 496 11 461 43 450 2 478 37 466 15 459 42 482 7 451 19 455 2 453 47 475 48 450 1 474 46 471 9 4...
output:
411 79401 9145270 673005095 180581065 984223118 -411655119 293043270 -593880557 -562183535 -448908149 198095539 532599404 578547658 783749571 403654694 -766957240 25290367 916754998 552459593 829894013 451078454 2259646 233624624 -768068180 -42781242 -565844967 -187717936 -158913393 -587634388 -8180...
result:
wrong answer 7th numbers differ - expected: '586589234', found: '-411655119'