QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203097 | #2482. Storage Problems | Rd_rainydays# | TL | 2ms | 18896kb | C++14 | 1.1kb | 2023-10-06 15:22:48 | 2023-10-06 15:22:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;++i)
static const int M=403;
static const int Mod=167772161;
int n,m,W[M];
int F[M][M][M],G[M][M][M];
int Ans[M][M];
int main(){
scanf("%d%d",&n,&m);
REP(i,1,n+1)scanf("%d",&W[i]);
F[0][0][0]=G[0][0][0]=1;
REP(i,1,n+1){
int w=W[i],v=W[n-i+1];
REP(j,0,i)REP(k,0,m+1){
if(F[i-1][j][k])
F[i][j][k]=F[i-1][j][k];
if(G[i-1][j][k])
G[i][j][k]=G[i-1][j][k];
}
REP(j,0,i)REP(k,0,m-w+1)
if(F[i-1][j][k])
F[i][j+1][k+w]=(F[i][j+1][k+w]+F[i-1][j][k])%Mod;
REP(j,0,i)REP(k,0,m-v+1)
if(G[i-1][j][k])
G[i][j+1][k+v]=(G[i][j+1][k+v]+G[i-1][j][k])%Mod;
}
memset(Ans,-1,sizeof(Ans));
REP(i,1,n+1){
int w=W[i];
if(Ans[w][1]==-1){
REP(j,1,n)Ans[w][j]=0;
REP(a,0,i)REP(j,1,m+1)
F[i-1][a][j]=(F[i-1][a][j]+F[i-1][a][j-1])%Mod;
REP(a,0,i)REP(b,0,n-i+1)
REP(j,0,m+1)
Ans[w][a+b]=(Ans[w][a+b]+1ll*G[n-i][b][j]*(F[i-1][a][m-j]+Mod-(m-j-w<0?0:F[i-1][a][m-j-w])))%Mod;
}
REP(j,1,n)printf("%d%c",Ans[w][j]," \n"[j==n-1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10696kb
input:
3 2 1 1 2
output:
1 0 1 0 2 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 10776kb
input:
3 3 2 2 1
output:
1 1 1 1 0 0
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 10476kb
input:
3 6 6 5 2
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 10724kb
input:
4 5 3 4 2 5
output:
2 0 0 3 1 0 2 0 0 3 1 0
result:
ok 4 lines
Test #5:
score: 0
Accepted
time: 1ms
memory: 10572kb
input:
3 6 1 1 5
output:
0 1 0 1 0 1
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 2ms
memory: 14652kb
input:
7 5 5 5 2 4 4 5 3
output:
6 1 0 0 0 0 6 1 0 0 0 0 5 0 0 0 0 0 6 1 0 0 0 0 6 1 0 0 0 0 6 1 0 0 0 0 5 0 0 0 0 0
result:
ok 7 lines
Test #7:
score: 0
Accepted
time: 2ms
memory: 12804kb
input:
4 6 2 4 4 5
output:
1 0 0 2 1 0 2 1 0 3 2 0
result:
ok 4 lines
Test #8:
score: 0
Accepted
time: 1ms
memory: 10724kb
input:
4 9 2 5 5 5
output:
0 0 0 2 2 0 2 2 0 2 2 0
result:
ok 4 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 14596kb
input:
4 5 5 3 1 3
output:
3 2 0 2 1 0 1 0 0 2 1 0
result:
ok 4 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 12676kb
input:
5 6 3 2 5 5 1
output:
2 2 0 0 2 2 0 0 3 4 1 0 3 4 1 0 0 0 0 0
result:
ok 5 lines
Test #11:
score: 0
Accepted
time: 1ms
memory: 12132kb
input:
4 5 5 2 1 5
output:
3 1 0 2 0 0 2 0 0 3 1 0
result:
ok 4 lines
Test #12:
score: 0
Accepted
time: 2ms
memory: 18652kb
input:
7 5 3 1 2 4 3 1 3
output:
3 10 3 0 0 0 0 4 0 0 0 0 1 8 3 0 0 0 4 12 4 0 0 0 3 10 3 0 0 0 0 4 0 0 0 0 3 10 3 0 0 0
result:
ok 7 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 16508kb
input:
6 8 8 1 8 4 2 1
output:
5 6 4 1 0 2 0 0 0 0 5 6 4 1 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0
result:
ok 6 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 12048kb
input:
5 6 6 5 5 5 6
output:
4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0
result:
ok 5 lines
Test #15:
score: 0
Accepted
time: 2ms
memory: 16548kb
input:
6 8 5 3 8 5 8 4
output:
4 2 0 0 0 2 0 0 0 0 5 3 0 0 0 4 2 0 0 0 5 3 0 0 0 4 2 0 0 0
result:
ok 6 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 14848kb
input:
4 8 3 4 7 4
output:
1 1 0 1 1 0 3 3 0 1 1 0
result:
ok 4 lines
Test #17:
score: 0
Accepted
time: 2ms
memory: 18572kb
input:
7 5 2 5 5 1 3 3 1
output:
2 4 2 0 0 0 6 9 3 0 0 0 6 9 3 0 0 0 2 2 0 0 0 0 3 5 2 0 0 0 3 5 2 0 0 0 2 2 0 0 0 0
result:
ok 7 lines
Test #18:
score: 0
Accepted
time: 0ms
memory: 14712kb
input:
4 9 3 7 5 3
output:
1 1 0 3 3 0 1 1 0 1 1 0
result:
ok 4 lines
Test #19:
score: 0
Accepted
time: 0ms
memory: 14812kb
input:
6 9 2 7 6 9 4 9
output:
2 0 0 0 0 4 2 0 0 0 4 2 0 0 0 5 3 0 0 0 4 2 0 0 0 5 3 0 0 0
result:
ok 6 lines
Test #20:
score: 0
Accepted
time: 0ms
memory: 14852kb
input:
7 7 2 1 2 4 7 7 6
output:
3 2 1 0 0 0 2 0 0 0 0 0 3 2 1 0 0 0 3 2 1 0 0 0 6 7 3 0 0 0 6 7 3 0 0 0 5 6 3 0 0 0
result:
ok 7 lines
Test #21:
score: 0
Accepted
time: 1ms
memory: 10696kb
input:
3 9 7 7 5
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #22:
score: 0
Accepted
time: 2ms
memory: 14724kb
input:
5 8 8 8 7 2 7
output:
4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0 4 0 0 0
result:
ok 5 lines
Test #23:
score: 0
Accepted
time: 1ms
memory: 14860kb
input:
5 9 5 3 6 9 8
output:
3 1 0 0 2 0 0 0 3 1 0 0 4 2 0 0 4 2 0 0
result:
ok 5 lines
Test #24:
score: 0
Accepted
time: 1ms
memory: 10756kb
input:
3 8 6 3 2
output:
1 1 1 1 0 0
result:
ok 3 lines
Test #25:
score: 0
Accepted
time: 1ms
memory: 10624kb
input:
3 6 6 6 4
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #26:
score: 0
Accepted
time: 1ms
memory: 16292kb
input:
7 5 4 3 3 5 5 1 4
output:
5 3 0 0 0 0 5 3 0 0 0 0 5 3 0 0 0 0 6 4 0 0 0 0 6 4 0 0 0 0 2 0 0 0 0 0 5 3 0 0 0 0
result:
ok 7 lines
Test #27:
score: 0
Accepted
time: 1ms
memory: 10584kb
input:
4 8 6 4 1 5
output:
2 2 0 2 2 0 0 0 0 2 2 0
result:
ok 4 lines
Test #28:
score: 0
Accepted
time: 1ms
memory: 14780kb
input:
6 8 5 6 3 8 7 6
output:
4 0 0 0 0 5 1 0 0 0 4 0 0 0 0 5 1 0 0 0 5 1 0 0 0 5 1 0 0 0
result:
ok 6 lines
Test #29:
score: 0
Accepted
time: 1ms
memory: 14788kb
input:
5 7 7 3 3 1 2
output:
4 6 3 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 0
result:
ok 5 lines
Test #30:
score: 0
Accepted
time: 0ms
memory: 18580kb
input:
7 8 4 7 1 5 2 5 4
output:
3 7 3 0 0 0 5 10 4 0 0 0 0 1 0 0 0 0 4 8 3 0 0 0 1 2 0 0 0 0 4 8 3 0 0 0 3 7 3 0 0 0
result:
ok 7 lines
Test #31:
score: 0
Accepted
time: 0ms
memory: 18896kb
input:
7 5 4 5 3 4 4 1 4
output:
5 4 0 0 0 0 6 5 0 0 0 0 5 4 0 0 0 0 5 4 0 0 0 0 5 4 0 0 0 0 1 0 0 0 0 0 5 4 0 0 0 0
result:
ok 7 lines
Test #32:
score: 0
Accepted
time: 0ms
memory: 10696kb
input:
4 8 3 8 5 8
output:
2 0 0 3 1 0 2 0 0 3 1 0
result:
ok 4 lines
Test #33:
score: -100
Time Limit Exceeded
input:
400 400 131 13 2 91 164 99 7 102 253 22 16 11 2 92 60 113 15 40 23 89 198 4 15 51 93 34 51 19 3 53 15 125 65 22 22 13 111 122 400 39 27 11 119 336 30 63 139 99 162 104 34 26 1 49 152 60 14 92 73 400 24 43 14 84 32 82 65 336 27 27 36 153 3 135 30 242 11 25 29 78 79 32 9 42 80 72 207 206 75 50 50 117 ...
output:
12 7156 1967080 119136539 34827776 81858977 124110671 61298833 76646242 34519046 58612716 91816388 91296622 115215838 101080005 22736412 57697102 136597697 164696207 77881601 52502636 48239559 5273941 63249857 39054255 89971302 93227129 26823160 48954324 89748626 159996761 118567485 85460269 1421088...