QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #394960 | #2482. Storage Problems | I_Love_Sonechka# | WA | 210ms | 4888kb | C++14 | 1.1kb | 2024-04-20 23:15:20 | 2024-04-20 23:15:20 |
Judging History
answer
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
const int mod = 167772161;
void add(int &a, int b) {
a += b;
if(a >= b) {
a -= mod;
}
if(a < 0) {
a += mod;
}
}
#define vt vector
int main() {
int n, k;
cin >> n >> k;
vt<int> a(n);
for(auto &x : a) {
cin >> x;
}
vt<vt<int>> dp(n + 1, vt<int>(k + 1, 0));
dp[0][0] = 1;
for(int i = 0; i < n; ++i) {
vt<vt<int>> ndp = dp;
for(int c = 0; c < n; ++ c) {
for(int w = 0; w < k; ++w) if(w + a[i] <= k) {
add(ndp[c + 1][w + a[i]], dp[c][w]);
}
}
swap(dp, ndp);
}
for(int i = 0; i < n; ++i) {
vt<int> res(n, 0);
vt<vt<int>> ndp = dp;
for(int c = 0; c < n; ++ c) {
for(int w = 0; w <= k; ++ w) {
if(w + a[i] <= k) {
add(ndp[c+1][w+a[i]], -ndp[c][w]);
}
if(w + a[i] > k) {
add(res[c], ndp[c][w]);
}
}
if(c) {
cout << res[c] << " ";
}
}
// for(auto v: ndp) {
// for(auto x: v) {
// cout << x << " ";
// }
// cout << "\n";
// }
cout << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
input:
3 2 1 1 2
output:
1 0 1 0 2 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
3 3 2 2 1
output:
1 1 1 1 0 0
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 3864kb
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: 3856kb
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: 0ms
memory: 3660kb
input:
3 6 1 1 5
output:
0 1 0 1 0 1
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 0ms
memory: 3564kb
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: 0ms
memory: 3604kb
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: 0ms
memory: 3564kb
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: 3564kb
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: 3584kb
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: 0ms
memory: 3516kb
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: 0ms
memory: 3596kb
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: 3856kb
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: 3828kb
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: 0ms
memory: 3792kb
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: 3628kb
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: 0ms
memory: 3628kb
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: 3624kb
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: 3812kb
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: 3568kb
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: 0ms
memory: 3868kb
input:
3 9 7 7 5
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #22:
score: 0
Accepted
time: 0ms
memory: 3628kb
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: 0ms
memory: 3596kb
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: 0ms
memory: 3788kb
input:
3 8 6 3 2
output:
1 1 1 1 0 0
result:
ok 3 lines
Test #25:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
3 6 6 6 4
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #26:
score: 0
Accepted
time: 0ms
memory: 3864kb
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: 0ms
memory: 3860kb
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: 0ms
memory: 3868kb
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: 0ms
memory: 3636kb
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: 3684kb
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: 3560kb
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: 3576kb
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
Wrong Answer
time: 210ms
memory: 4888kb
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...
result:
wrong answer 1st lines differ - expected: '12 7156 1967080 119136539 3482...0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0', found: '12 7156 1967080 119136539 3482... 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 '