QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #762228 | #8225. 最小值之和 | rizynvu | 36 | 40ms | 12504kb | C++14 | 1.2kb | 2024-11-19 14:14:01 | 2024-11-19 14:14:10 |
Judging History
answer
#include<bits/stdc++.h>
constexpr int maxn = 50 + 5, maxm = maxn * maxn;
int n, m;
int a[maxn], b[maxn];
bool f[maxn][maxn][maxm];
void dfs(int l, int r, int val) {
if (l == r) return ;
for (int c = 0; ; c++, val += r - l) {
for (int p = l; p < r; p++) {
if (f[l][p][val] && f[p + 1][r][val]) {
dfs(l, p, val), dfs(p + 1, r, val);
b[l] += c, b[r] -= c;
return ;
}
}
}
}
int main() {
scanf("%d", &n), m = (n - 1) * 50;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
if (a[i] > m) {
return puts("No"), 0;
}
f[i][i][a[i]] = 1;
}
for (int len = 2; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
for (int p = l; p < r; p++) {
for (int val = 0; val <= m; val++) {
f[l][r][val] |= f[l][p][val] & f[p + 1][r][val];
}
}
for (int val = m; ~ val; val--) {
f[l][r][val] |= f[l][r][val + len - 1];
}
}
}
if (! f[1][n][0]) {
return puts("No"), 0;
}
puts("Yes");
dfs(1, n, 0);
for (int i = 1; i < n; i++) {
printf("%d ", b[i] += b[i - 1]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 0ms
memory: 3956kb
input:
5 14 14 12 13 13
output:
Yes 14 0 6 7
result:
ok The answer is correct.
Test #2:
score: 11
Accepted
time: 1ms
memory: 5968kb
input:
5 4 4 7 7 4
output:
Yes 4 0 5 2
result:
ok The answer is correct.
Test #3:
score: 11
Accepted
time: 0ms
memory: 3952kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 11
Accepted
time: 0ms
memory: 3820kb
input:
5 11 11 10 5 5
output:
Yes 6 5 0 5
result:
ok The answer is correct.
Test #5:
score: 11
Accepted
time: 1ms
memory: 5960kb
input:
5 10 10 10 4 4
output:
Yes 5 5 0 4
result:
ok The answer is correct.
Test #6:
score: 11
Accepted
time: 0ms
memory: 3972kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 11
Accepted
time: 0ms
memory: 3956kb
input:
5 12 12 16 19 19
output:
Yes 12 0 8 11
result:
ok The answer is correct.
Test #8:
score: 11
Accepted
time: 0ms
memory: 3952kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 11
Accepted
time: 0ms
memory: 3880kb
input:
5 10 10 8 5 5
output:
Yes 6 4 0 5
result:
ok The answer is correct.
Test #10:
score: 11
Accepted
time: 0ms
memory: 3832kb
input:
5 24 24 28 28 26
output:
Yes 24 0 15 13
result:
ok The answer is correct.
Test #11:
score: 11
Accepted
time: 0ms
memory: 3984kb
input:
5 5 5 22 31 31
output:
Yes 5 0 11 20
result:
ok The answer is correct.
Test #12:
score: 11
Accepted
time: 0ms
memory: 4008kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 11
Accepted
time: 0ms
memory: 3940kb
input:
5 16 16 4 12 12
output:
Yes 16 0 2 10
result:
ok The answer is correct.
Test #14:
score: 11
Accepted
time: 0ms
memory: 4000kb
input:
5 29 29 24 26 26
output:
Yes 29 0 12 14
result:
ok The answer is correct.
Test #15:
score: 11
Accepted
time: 0ms
memory: 3908kb
input:
5 0 33 33 32 32
output:
Yes 0 33 0 32
result:
ok The answer is correct.
Test #16:
score: 11
Accepted
time: 0ms
memory: 5816kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 11
Accepted
time: 1ms
memory: 5936kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 11
Accepted
time: 1ms
memory: 5724kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 11
Accepted
time: 0ms
memory: 3832kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 11
Accepted
time: 1ms
memory: 5652kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 11
Accepted
time: 0ms
memory: 3872kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 11
Accepted
time: 1ms
memory: 5972kb
input:
5 6 7 7 6 6
output:
Yes 3 4 0 6
result:
ok The answer is correct.
Test #23:
score: 11
Accepted
time: 0ms
memory: 3964kb
input:
5 25 25 24 20 20
output:
Yes 13 12 0 20
result:
ok The answer is correct.
Test #24:
score: 11
Accepted
time: 1ms
memory: 5852kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 11
Accepted
time: 1ms
memory: 5796kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 11
Accepted
time: 0ms
memory: 5876kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 11
Accepted
time: 0ms
memory: 3876kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 11
Accepted
time: 0ms
memory: 3688kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 11
Accepted
time: 0ms
memory: 3832kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 11
Accepted
time: 0ms
memory: 3888kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 11
Accepted
time: 0ms
memory: 3792kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 11
Accepted
time: 0ms
memory: 3880kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 11
Accepted
time: 0ms
memory: 3784kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 11
Accepted
time: 0ms
memory: 3784kb
input:
1 233
output:
No
result:
ok The answer is correct.
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #35:
score: 15
Accepted
time: 1ms
memory: 6068kb
input:
8 16 16 8 8 9 9 6 6
output:
Yes 16 0 8 0 9 0 6
result:
ok The answer is correct.
Test #36:
score: 15
Accepted
time: 0ms
memory: 3948kb
input:
8 16 16 9 21 21 23 23 23
output:
Yes 16 0 3 15 1 10 10
result:
ok The answer is correct.
Test #37:
score: 15
Accepted
time: 1ms
memory: 5968kb
input:
8 10 10 15 15 15 10 10 5
output:
Yes 10 0 6 6 1 6 1
result:
ok The answer is correct.
Test #38:
score: 15
Accepted
time: 1ms
memory: 5996kb
input:
8 13 13 15 15 24 24 24 10
output:
Yes 13 0 7 2 9 9 2
result:
ok The answer is correct.
Test #39:
score: 15
Accepted
time: 0ms
memory: 4024kb
input:
8 5 13 16 25 25 24 4 4
output:
Yes 1 3 4 9 8 0 4
result:
ok The answer is correct.
Test #40:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
No
result:
wrong answer Line 1 expected 0
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Test #77:
score: 25
Accepted
time: 33ms
memory: 10892kb
input:
49 28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4
output:
Yes 14 14 0 12 25 0 15 18 1 13 27 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1
result:
ok The answer is correct.
Test #78:
score: 25
Accepted
time: 37ms
memory: 12132kb
input:
49 3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4
output:
Yes 3 0 29 0 31 0 34 0 17 14 1 10 9 0 21 0 36 0 11 14 13 2 14 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 60 0 4 2
result:
ok The answer is correct.
Test #79:
score: 25
Accepted
time: 37ms
memory: 12244kb
input:
49 18 18 18 16 16 59 61 64 64 57 57 78 78 78 78 81 92 92 92 92 89 81 47 64 64 63 59 65 65 63 52 52 34 34 33 8 13 13 17 17 14 16 19 19 13 13 18 18 18
output:
Yes 9 9 0 16 0 19 20 23 1 53 0 78 0 78 0 36 47 1 28 25 21 3 8 15 14 12 0 31 29 1 46 1 15 14 0 4 9 0 17 0 4 5 8 1 9 0 9 9
result:
ok The answer is correct.
Test #80:
score: 25
Accepted
time: 40ms
memory: 12148kb
input:
50 43 47 47 42 42 41 51 51 57 62 62 61 58 58 67 67 68 68 63 68 68 67 71 71 76 76 76 76 76 76 48 48 48 48 36 36 33 33 4 8 8 6 6 11 11 3 3 10 10 10
output:
Yes 20 24 1 20 19 0 51 0 19 22 21 0 58 0 67 0 68 0 21 24 23 0 71 0 76 0 76 0 76 0 48 0 48 0 36 0 33 0 2 6 0 6 0 11 0 3 0 5 5
result:
ok The answer is correct.
Test #81:
score: 25
Accepted
time: 37ms
memory: 12028kb
input:
49 12 14 14 16 16 10 18 32 32 30 30 0 0 5 5 4 0 9 9 18 18 18 30 41 43 43 39 39 35 24 26 27 27 6 6 13 13 19 22 22 21 21 44 44 43 43 33 33 31
output:
Yes 6 8 0 16 0 2 6 20 2 22 0 0 0 3 2 0 0 9 0 9 9 0 5 9 11 6 10 6 0 8 9 10 0 6 0 13 0 5 8 1 11 1 34 1 33 1 13 11
result:
ok The answer is correct.
Test #82:
score: 25
Accepted
time: 34ms
memory: 10580kb
input:
48 13 13 11 3 36 40 40 40 36 35 35 30 18 18 33 33 33 23 20 20 17 19 20 20 0 10 31 31 28 30 30 5 16 16 13 12 12 36 39 39 37 37 25 25 26 26 7 7
output:
Yes 7 5 1 0 9 11 11 9 0 20 15 0 14 1 12 12 7 0 16 1 5 6 7 0 0 5 26 0 14 16 0 1 8 5 1 8 0 18 21 0 37 0 25 0 26 0 7
result:
ok The answer is correct.
Test #83:
score: 25
Accepted
time: 33ms
memory: 11308kb
input:
49 72 72 71 33 98 98 89 89 174 174 163 163 170 170 82 98 98 202 202 179 164 282 299 299 316 316 300 262 250 250 236 154 140 148 150 150 148 148 131 95 95 106 106 108 108 81 78 78 51
output:
Yes 31 30 11 0 98 0 89 0 174 0 163 0 170 0 41 57 0 102 79 1 48 107 124 1 113 97 78 3 97 83 42 1 40 44 46 1 72 55 1 73 0 106 0 66 39 1 51 24
result:
ok The answer is correct.
Test #84:
score: 25
Accepted
time: 40ms
memory: 12100kb
input:
50 148 360 360 392 392 399 399 384 350 350 346 346 306 306 314 314 346 346 323 321 174 293 299 304 342 342 340 328 328 227 227 192 330 339 339 318 327 327 326 266 266 182 204 204 67 67 79 79 85 85
output:
Yes 74 286 0 392 0 207 192 0 350 0 346 0 306 0 314 0 131 108 107 0 21 38 39 40 60 58 40 64 3 200 0 64 133 142 0 106 111 110 0 266 0 91 113 0 67 0 79 0 85
result:
ok The answer is correct.
Test #85:
score: 25
Accepted
time: 31ms
memory: 12116kb
input:
48 200 224 224 200 267 267 259 231 246 246 215 215 196 184 180 180 270 270 270 234 230 233 233 186 114 165 165 160 190 212 212 243 243 239 239 143 143 162 162 262 264 264 246 234 238 238 22 22
output:
Yes 100 124 0 31 67 59 32 45 60 1 80 61 55 2 157 1 89 89 71 2 77 80 55 0 57 108 0 52 67 89 2 235 0 239 0 143 0 162 0 90 92 82 0 117 121 0 22
result:
ok The answer is correct.
Test #86:
score: 25
Accepted
time: 37ms
memory: 12296kb
input:
49 226 226 216 196 196 158 193 253 253 257 257 257 201 300 300 320 384 392 392 385 385 263 291 291 269 287 287 277 277 487 487 497 497 496 482 507 511 511 503 331 152 173 189 214 214 232 232 221 191
output:
Yes 118 108 0 196 0 23 39 99 24 71 71 2 83 182 3 96 128 136 3 236 114 0 291 0 128 146 1 263 1 455 3 121 120 41 77 86 90 84 40 0 37 44 52 77 1 88 77 62
result:
ok The answer is correct.
Test #87:
score: 25
Accepted
time: 37ms
memory: 11356kb
input:
49 247 247 231 383 383 381 379 398 398 397 391 195 200 227 227 197 197 339 339 337 344 344 379 388 388 379 343 405 405 412 412 402 402 412 412 398 398 415 430 430 382 382 384 384 341 198 122 124 124
output:
Yes 247 0 77 154 152 0 85 93 92 89 39 0 100 127 0 197 0 339 0 166 173 1 97 106 97 85 0 405 0 412 0 402 0 412 0 398 0 130 145 25 202 25 136 93 24 2 52 54
result:
ok The answer is correct.
Test #88:
score: 25
Accepted
time: 30ms
memory: 11184kb
input:
48 196 196 284 284 280 280 263 303 387 387 388 388 343 321 321 328 328 283 283 151 157 157 164 164 198 203 203 172 166 178 259 280 294 294 288 243 239 239 235 226 226 330 333 333 302 287 295 295
output:
Yes 196 0 284 0 280 0 81 101 185 3 205 160 3 295 1 316 1 202 70 0 157 0 164 0 53 58 40 38 2 28 45 52 62 56 41 0 118 114 1 213 2 89 92 75 70 0 295
result:
ok The answer is correct.
Test #89:
score: 25
Accepted
time: 30ms
memory: 10764kb
input:
48 244 256 256 248 253 253 269 269 250 229 229 67 252 322 261 116 372 271 372 322 333 333 393 429 429 428 347 319 294 387 234 352 370 370 317 37 193 398 10 76 215 222 222 208 344 145 171 87
output:
No
result:
ok The answer is correct.
Test #90:
score: 25
Accepted
time: 40ms
memory: 12456kb
input:
50 34 15 33 66 66 66 33 39 9 35 55 29 34 35 51 13 50 50 56 48 44 43 57 57 57 25 50 50 27 27 21 47 35 50 50 55 55 53 7 43 37 55 55 62 62 62 52 21 26 26
output:
No
result:
ok The answer is correct.
Test #91:
score: 25
Accepted
time: 37ms
memory: 12504kb
input:
49 47 64 64 64 59 74 74 3 72 19 67 71 25 61 61 58 50 49 49 58 62 70 70 69 51 70 62 62 62 62 62 54 8 41 41 41 19 40 40 20 8 24 24 20 16 16 16 19 19
output:
No
result:
ok The answer is correct.
Test #92:
score: 25
Accepted
time: 34ms
memory: 12100kb
input:
48 13 13 10 27 27 28 28 18 29 29 26 24 31 31 30 26 12 12 0 0 0 42 42 38 38 38 37 37 27 27 26 60 60 68 70 70 67 67 70 70 67 67 48 49 49 47 47 44
output:
Yes 13 0 5 22 0 19 9 0 12 9 8 0 11 10 8 1 8 0 0 0 0 42 0 19 19 0 37 0 27 0 13 47 0 34 36 0 67 0 70 0 67 0 24 25 0 25 22
result:
ok The answer is correct.
Test #93:
score: 25
Accepted
time: 40ms
memory: 10724kb
input:
50 22 22 14 24 27 27 25 25 10 47 47 45 41 42 42 44 44 43 43 0 32 32 30 27 27 10 10 14 14 14 4 11 11 9 23 23 20 28 28 22 29 31 1 28 30 30 30 30 27 27
output:
No
result:
ok The answer is correct.
Test #94:
score: 25
Accepted
time: 33ms
memory: 12164kb
input:
49 45 69 69 73 73 73 69 69 34 34 31 47 51 54 54 58 58 56 56 53 42 42 10 10 4 7 7 60 61 61 63 63 64 66 66 62 34 49 49 49 46 40 38 43 43 13 13 10 10
output:
No
result:
ok The answer is correct.
Test #95:
score: 25
Accepted
time: 35ms
memory: 11356kb
input:
48 17 17 16 16 0 27 29 32 32 36 36 39 39 35 33 21 23 23 46 46 46 46 38 38 36 36 34 34 31 33 33 36 36 30 30 28 28 23 19 19 33 37 37 15 38 39 39 0
output:
No
result:
ok The answer is correct.
Test #96:
score: 25
Accepted
time: 37ms
memory: 10848kb
input:
49 18 25 25 24 30 31 31 32 32 31 27 43 43 48 48 53 53 51 39 48 48 47 47 11 11 53 28 24 24 23 21 24 24 24 24 19 38 39 39 38 38 39 42 42 41 36 39 39 37
output:
No
result:
ok The answer is correct.
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%