QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #203128 | #2482. Storage Problems | Delay_for_five_minutes# | TL | 1ms | 5908kb | C++11 | 1.3kb | 2023-10-06 15:39:48 | 2023-10-06 15:39:48 |
Judging History
answer
#include<bits/stdc++.h>
#define maxn 405
const int mod = 167772161;
int w[maxn];
int ans[maxn][maxn];
int Mod(int x) {return x >= mod ? x - mod : x;}
void work(int f[][maxn], int l, int r, int K) {
f[0][0] = 1;
for(int i = 1; i <= r - l + 1; i++) {
for(int j = 0; j <= K; j++) {
f[i][j] = 0;
}
}
for(int i = l; i <= r; i++) {
for(int j = i - l + 1; j >= 1; j--) {
for(int t = K; t >= w[i]; t--) {
f[j][t] = Mod( f[j][t] + f[j - 1][t - w[i]] );
}
}
}
}
void solve(int l,int r,int K,int pret,int pref) {
if (l == r) {
if (K < w[l])
ans[l][pret] = (ans[l][pret] + pref) % mod;
return ;
}
int f[maxn][maxn];
int mid = (l + r) >> 1;
work(f, l, mid, K);
for(int i = 0; i <= mid - l + 1; i++) {
for(int j = 0; j <= K; j++) if (f[i][j]) {
solve(mid + 1, r, K - j, pret + i, 1ll * pref * f[i][j] % mod);
}
}
work(f,mid + 1, r, K);
for(int i = 0; i <= r - mid; i++) {
for(int j = 0; j <= K; j++) if (f[i][j]) {
solve(l, mid, K - j, pret + i, 1ll * pref * f[i][j] % mod);
}
}
}
int main() {
int N,K;
std::cin >> N >> K;
for(int i = 1; i <= N; i++) {
std::cin >> w[i];
}
solve(1,N,K,0,1);
for(int i = 1; i <= N; i++) {
for(int j = 1; j < N; j++) {
printf("%d ",ans[i][j]);
}
putchar('\n');
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5084kb
input:
3 2 1 1 2
output:
1 0 1 0 2 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 5192kb
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: 5148kb
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: 5084kb
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: 5264kb
input:
3 6 1 1 5
output:
0 1 0 1 0 1
result:
ok 3 lines
Test #6:
score: 0
Accepted
time: 1ms
memory: 5712kb
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: 1ms
memory: 5132kb
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: 5152kb
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: 5156kb
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: 1ms
memory: 5772kb
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: 5080kb
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: 1ms
memory: 5712kb
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: 1ms
memory: 5700kb
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: 5784kb
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: 1ms
memory: 5904kb
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: 5196kb
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: 1ms
memory: 5776kb
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: 5156kb
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: 1ms
memory: 5724kb
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: 1ms
memory: 5724kb
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: 5136kb
input:
3 9 7 7 5
output:
2 0 2 0 2 0
result:
ok 3 lines
Test #22:
score: 0
Accepted
time: 1ms
memory: 5796kb
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: 5716kb
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: 5068kb
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: 5156kb
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: 5800kb
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: 5140kb
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: 5908kb
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: 5732kb
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: 5800kb
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: 5712kb
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: 5260kb
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 ...