QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #203155 | #2482. Storage Problems | Vengeful_Spirit# | WA | 906ms | 470836kb | C++14 | 2.2kb | 2023-10-06 15:51:46 | 2023-10-06 15:51:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 405, mod = 167772161;
int a[N], pr[N][N][N], sf[N][N][N], id[N];
vector<int> ans[N];
int add(int x, int y) {
return (x + y) % mod;
}
void Add(int &x, int y) {
x = add(x, y);
}
int mul(int x, int y) {
return 1ll * x * y;
}
void Mul(int &x, int y) {
x = mul(x, y);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, K;
cin >> n >> K;
for(int i = 1; i <= n; ++i) cin >> a[i], id[i] = i;
sort(id+1, id+n+1, [&](int x, int y)->bool{
return a[x] < a[y];
});
sort(a+1, a+n+1);
pr[0][0][0] = sf[n+1][0][0] = 1;
for(int i = 1; i <= n; ++i) {
pr[i][0][0] = 1;
for(int j = 1; j <= i; ++j) for(int k = 0; k < N; ++k) {
Add(pr[i][j][k], pr[i - 1][j][k]);
if(k >= a[i]) Add(pr[i][j][k], pr[i - 1][j - 1][k - a[i]]);
}
}
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= i; ++j) for(int k = 1; k < N; ++k)
Add(pr[i][j][k], pr[i][j][k-1]);
}
for(int i = n; i >= 1; --i) {
sf[i][0][0] = 1;
for(int j = 1; j <= (n - i + 1); ++j) for(int k = 0; k < N; ++k) {
Add(sf[i][j][k], sf[i + 1][j][k]);
if(k >= a[i]) Add(sf[i][j][k], sf[i + 1][j - 1][k - a[i]]);
}
}
for(int i = 1; i <= n; ++i) {
if(a[i] == a[i-1]) {
ans[id[i]] = ans[id[i-1]];
continue;
}
ans[id[i]].resize(n);
int UP = min(n, K/a[i]);
for(int r = 0; r <= UP; ++r) {
for(int l = 0; l <= n-1-r; ++l) if(l + r > 0) {
for(int nr = 0; nr <= K; ++nr) if(sf[i+1][r][nr]) {
int _l = max(K-a[i]+1-nr, 0), _r = K-nr;
if(_l <= _r) {
int NUM = pr[i-1][l][_r];
if(_l) NUM = add(NUM, mod - pr[i-1][l][_l-1]);
Add(ans[id[i]][l+r], mul(sf[i+1][r][nr], NUM));
}
}
}
}
}
for(int i = 1; i <= n; ++i) {
for(int j = 1; j < n; ++j) {
cout << ans[i][j] << " " ;
}
cout << "\n";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 9520kb
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: 11656kb
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: 9720kb
input:
3 6 6 5 2
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #4:
score: 0
Accepted
time: 1ms
memory: 9788kb
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: 11648kb
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: 15928kb
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: 9528kb
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: 11664kb
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: 1ms
memory: 9608kb
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: 11804kb
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: 2ms
memory: 11716kb
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: 15776kb
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: 13868kb
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: 2ms
memory: 13836kb
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: 13704kb
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: 1ms
memory: 11692kb
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: 13728kb
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: 1ms
memory: 11616kb
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: 2ms
memory: 13648kb
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: 13732kb
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: 11644kb
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: 13692kb
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: 2ms
memory: 11560kb
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: 2ms
memory: 9612kb
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: 9780kb
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: 15920kb
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: 2ms
memory: 11712kb
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: 11680kb
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: 11676kb
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: 2ms
memory: 13884kb
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: 13672kb
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: 1ms
memory: 9516kb
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: 906ms
memory: 470836kb
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 23447400 61298833 76646242 34519046 125721606 91816388 158405512 115215838 416734 22736412 57697102 35934426 64032936 77881601 119611526 48239559 5273941 63249857 39054255 89971302 93227129 26823160 48954324 89748626 159996761 118567485 85460269 142108841 ...
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 '