QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331015 | #8225. 最小值之和 | djwj233 | 39 | 609ms | 6136kb | C++14 | 2.4kb | 2024-02-17 22:14:52 | 2024-02-17 22:14:52 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fo(v, a, b) for(int v = a; v <= b; v++)
#define fr(v, a, b) for(int v = a; v >= b; v--)
#define cl(a, v) memset(a, v, sizeof(a))
const int N = 82, M = 6410;
int n, m, a[N], b[N];
int dp[N][N][N];
void solve(int l, int r, int x) {
if(l == r) return ;
int L = r - l, now = 0;
while(true) {
fo(p, l, r - 1) {
int A = p - l, B = r - 1 - p;
if(((A == 0 && x == b[l]) || (A && dp[l][p][x % A] >= x)) &&
((B == 0 && x == b[r]) || (B && dp[p + 1][r][x % B] >= x))) {
solve(l, p, x), solve(p + 1, r, x);
fo(i, l, r - 1) a[i] += now;
return ;
}
}
x += L, now++;
}
}
inline int lcm(int x, int y) {
if(!x || !y) return x | y;
return x / __gcd(x, y) * y;
}
inline void upd(int &x, int y) { x = max(x, y); }
inline int calc(int Z, int i, int lim) {
int c = (lim / Z) * Z + i;
return c > lim ? c - Z : c;
}
int val[N];
int main()
{
scanf("%d", &n); fo(i, 1, n) scanf("%d", &b[i]);
if(n == 1) {
if(b[1]) puts("No"); else puts("Yes"), puts("");
exit(0);
}
cl(dp, 0xff);
fo(len, 2, n) fo(l, 1, n - len + 1) {
int r = l + len - 1, L = r - l;
if(len == 2) {
if(b[l] == b[r]) dp[l][r][0] = b[l];
continue;
}
fo(p, l, r - 1) {
int A = p - l, B = r - 1 - p;
if(A == 0) {
int v = b[l];
if(dp[p + 1][r][v % B] >= v) upd(dp[l][r][v % L], v);
continue;
}
if(B == 0) {
int v = b[r];
if(dp[l][p][v % A] >= v) upd(dp[l][r][v % L], v);
continue;
}
int C = lcm(A, B); cl(val, 0xff);
for(int i = 0; i < C; i++) {
int cur = min(calc(C, i, dp[l][p][i % A]), calc(C, i, dp[p + 1][r][i % B]));
if(cur >= 0) upd(val[cur % L], cur);
}
fo(t, 0, 1) fo(i, 0, L - 1) upd(val[(i - C) % L], val[i] - C);
fo(i, 0, L - 1) upd(dp[l][r][i], val[i]);
}
}
if(dp[1][n][0] < 0) puts("No"), exit(0);
puts("Yes"), solve(1, n, 0);
fo(i, 1, n - 1) printf("%d ", a[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 1ms
memory: 6064kb
input:
5 14 14 12 13 13
output:
Yes 14 0 6 7
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 1ms
memory: 6128kb
input:
5 4 4 7 7 4
output:
Yes 4 0 5 2
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 1ms
memory: 6080kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 1ms
memory: 6128kb
input:
5 11 11 10 5 5
output:
Yes 6 5 0 5
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 1ms
memory: 6024kb
input:
5 10 10 10 4 4
output:
Yes 5 5 0 4
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 0ms
memory: 6088kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 1ms
memory: 6028kb
input:
5 12 12 16 19 19
output:
Yes 12 0 8 11
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
5 10 10 8 5 5
output:
Yes 6 4 0 5
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 0ms
memory: 6000kb
input:
5 24 24 28 28 26
output:
Yes 24 0 15 13
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
5 5 5 22 31 31
output:
Yes 5 0 11 20
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 0ms
memory: 5944kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 0ms
memory: 6036kb
input:
5 16 16 4 12 12
output:
Yes 16 0 2 10
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 1ms
memory: 5940kb
input:
5 29 29 24 26 26
output:
Yes 29 0 12 14
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 0ms
memory: 6080kb
input:
5 0 33 33 32 32
output:
Yes 0 33 0 32
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 1ms
memory: 5896kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 0ms
memory: 5820kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 1ms
memory: 6020kb
input:
5 6 7 7 6 6
output:
Yes 3 4 0 6
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 1ms
memory: 6064kb
input:
5 25 25 24 20 20
output:
Yes 13 12 0 20
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 0ms
memory: 6020kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 6000kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 0ms
memory: 5956kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 5952kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 0ms
memory: 6068kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
1 233
output:
No
result:
ok The answer is correct.
Subtask #2:
score: 15
Accepted
Dependency #1:
100%
Accepted
Test #35:
score: 15
Accepted
time: 1ms
memory: 6132kb
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: 0
Accepted
time: 0ms
memory: 6128kb
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: 0
Accepted
time: 1ms
memory: 6020kb
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: 0
Accepted
time: 1ms
memory: 6084kb
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: 0
Accepted
time: 1ms
memory: 6084kb
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
Accepted
time: 1ms
memory: 6028kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
Yes 649 1031 3 766 348 3 539
result:
ok The answer is correct.
Test #41:
score: 0
Accepted
time: 1ms
memory: 6132kb
input:
8 1386 1416 1416 1069 1069 390 645 645
output:
Yes 693 723 0 1069 0 195 450
result:
ok The answer is correct.
Test #42:
score: 0
Accepted
time: 1ms
memory: 6132kb
input:
8 3377 3377 3164 3164 3570 3570 3365 3365
output:
Yes 3377 0 3164 0 3570 0 3365
result:
ok The answer is correct.
Test #43:
score: 0
Accepted
time: 89ms
memory: 6068kb
input:
8 28167709 33181201 33829300 33829300 21924091 26145199 28398185 28398185
output:
Yes 9389235 11895981 12544080 1 7308029 9418583 11671569
result:
ok The answer is correct.
Test #44:
score: 0
Accepted
time: 50ms
memory: 6092kb
input:
8 4726918 12793592 12793592 6681214 13995142 22020836 22566624 22566624
output:
Yes 1575638 8665164 2552786 1 4665046 8677893 9223681
result:
ok The answer is correct.
Test #45:
score: 0
Accepted
time: 88ms
memory: 6024kb
input:
8 9146297 15736298 15736298 16471005 16471005 14187656 14187656 6001415
output:
Yes 4573146 11163147 1 16470999 1 11186946 3000705
result:
ok The answer is correct.
Test #46:
score: 0
Accepted
time: 92ms
memory: 6124kb
input:
8 25115296 25115296 22120670 21035156 20603135 28703897 28703897 27553199
output:
Yes 8832173 5837547 5294790 5150783 1 14927295 13776597
result:
ok The answer is correct.
Test #47:
score: 0
Accepted
time: 173ms
memory: 5968kb
input:
8 22440147 22440147 22626721 22626721 22592252 22592252 19174074 19174074
output:
Yes 22440147 0 22626721 0 22592252 0 19174074
result:
ok The answer is correct.
Test #48:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
8 12 0 13 8 18 18 18 0
output:
No
result:
ok The answer is correct.
Test #49:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
8 3 23 13 18 26 12 25 25
output:
No
result:
ok The answer is correct.
Test #50:
score: 0
Accepted
time: 0ms
memory: 5820kb
input:
8 1353255 1004808 981534 1400692 1246708 409750 1177255 1177255
output:
No
result:
ok The answer is correct.
Test #51:
score: 0
Accepted
time: 0ms
memory: 5996kb
input:
8 96 96 99 99 4 94 39 36
output:
No
result:
ok The answer is correct.
Test #52:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
8 15 21 0 20 20 15 13 6
output:
No
result:
ok The answer is correct.
Test #53:
score: 0
Accepted
time: 1ms
memory: 5992kb
input:
8 2 1 0 2 6 6 5 1
output:
No
result:
ok The answer is correct.
Test #54:
score: 0
Accepted
time: 1ms
memory: 5892kb
input:
8 7 12 11 11 1 11 4 11
output:
No
result:
ok The answer is correct.
Test #55:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
8 18 3 27 27 19 10 6 6
output:
No
result:
ok The answer is correct.
Subtask #3:
score: 13
Accepted
Dependency #2:
100%
Accepted
Test #56:
score: 13
Accepted
time: 1ms
memory: 6136kb
input:
14 10 10 2 30 45 50 50 47 47 47 46 33 33 32
output:
Yes 9 1 0 6 11 15 12 1 20 19 1 13 12
result:
ok The answer is correct.
Test #57:
score: 0
Accepted
time: 0ms
memory: 6004kb
input:
14 0 19 19 16 16 4 0 36 36 36 36 31 31 26
output:
Yes 0 19 0 14 2 0 0 36 0 36 0 18 13
result:
ok The answer is correct.
Test #58:
score: 0
Accepted
time: 1ms
memory: 5996kb
input:
14 37 38 38 37 28 27 27 28 28 10 17 17 12 4
output:
Yes 10 11 10 7 0 27 0 28 0 3 9 4 1
result:
ok The answer is correct.
Test #59:
score: 0
Accepted
time: 1ms
memory: 6040kb
input:
14 13 27 33 33 30 30 31 31 20 20 25 25 24 24
output:
Yes 3 10 16 2 22 0 31 0 20 0 25 0 24
result:
ok The answer is correct.
Test #60:
score: 0
Accepted
time: 0ms
memory: 5916kb
input:
14 50 50 52 52 54 60 62 62 62 33 33 28 34 34
output:
Yes 50 0 52 0 13 15 16 16 1 28 0 14 20
result:
ok The answer is correct.
Test #61:
score: 0
Accepted
time: 1ms
memory: 6124kb
input:
14 5123 5321 5321 5600 5600 5161 5537 5537 5359 4679 4679 4128 4128 3029
output:
Yes 2556 2754 1 5588 1 1717 1994 1816 1 4667 1 2608 1509
result:
ok The answer is correct.
Test #62:
score: 0
Accepted
time: 0ms
memory: 5992kb
input:
14 340 2315 2315 2251 2251 1200 1366 1366 2831 2831 2864 2864 2812 2680
output:
Yes 170 2145 0 2251 0 600 766 0 2823 2 1010 958 892
result:
ok The answer is correct.
Test #63:
score: 0
Accepted
time: 0ms
memory: 6028kb
input:
14 681 810 2276 2390 2390 1189 2424 2424 2031 1180 2548 2620 2620 221
output:
Yes 168 211 944 1058 1 269 1083 690 266 28 1188 1260 27
result:
ok The answer is correct.
Test #64:
score: 0
Accepted
time: 561ms
memory: 6080kb
input:
14 37026886 40993600 44483477 44483477 41071802 57414984 57414984 60000010 60000010 64898381 64898381 63120240 63120240 58440430
output:
Yes 9256721 10578959 14029735 10618060 1 57414979 0 60000010 0 64898381 0 33900025 29220215
result:
ok The answer is correct.
Test #65:
score: 0
Accepted
time: 409ms
memory: 5944kb
input:
14 49671403 50230564 50230564 63423001 63423001 62198273 62452752 62452752 44987219 48671053 49604115 49604115 20314360 20314360
output:
Yes 24835699 25394860 1 63422995 1 31099134 31353613 0 14995739 16837656 17770718 1 20314356
result:
ok The answer is correct.
Test #66:
score: 0
Accepted
time: 299ms
memory: 6132kb
input:
14 17008521 17008521 17440120 44338597 44338597 42528453 45138523 45138523 43354927 34182290 34182290 33775196 33775196 32314840
output:
Yes 17008521 0 8720060 35618537 0 14176151 16372984 14589388 0 34182290 0 17617776 16157420
result:
ok The answer is correct.
Test #67:
score: 0
Accepted
time: 114ms
memory: 6068kb
input:
14 17784224 17784224 16246661 3452639 30562832 30928394 31034175 31034175 17501619 21436456 21436456 5363633 5661668 5661668
output:
Yes 9660888 8123325 1 863156 9899887 10082668 10188449 2 8750800 12685637 2 2681807 2979842
result:
ok The answer is correct.
Test #68:
score: 0
Accepted
time: 609ms
memory: 6088kb
input:
14 69235639 69235639 68987597 68987597 57039158 57039158 55926434 63346321 63346321 66237443 66237443 64858399 62617841 60839024
output:
Yes 69235639 0 68987597 0 57039158 0 27963217 35383104 0 18302018 16922974 15802695 15209756
result:
ok The answer is correct.
Test #69:
score: 0
Accepted
time: 0ms
memory: 6016kb
input:
14 87 74 86 89 86 79 79 14 37 9 33 33 38 38
output:
No
result:
ok The answer is correct.
Test #70:
score: 0
Accepted
time: 1ms
memory: 6004kb
input:
14 8 10 24 23 23 19 31 30 15 16 2 23 34 27
output:
No
result:
ok The answer is correct.
Test #71:
score: 0
Accepted
time: 0ms
memory: 5960kb
input:
14 72 72 72 64 72 62 15 15 42 42 6 26 43 25
output:
No
result:
ok The answer is correct.
Test #72:
score: 0
Accepted
time: 1ms
memory: 5936kb
input:
14 124 125 103 108 120 120 121 127 130 130 69 43 48 48
output:
No
result:
ok The answer is correct.
Test #73:
score: 0
Accepted
time: 1ms
memory: 6024kb
input:
14 18 3 16 11 11 24 24 25 25 10 14 17 13 10
output:
No
result:
ok The answer is correct.
Test #74:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
14 1432833 514825 398091 1958543 1337446 1729822 2090128 1970313 1970313 2487044 1900924 2317778 425241 425241
output:
No
result:
ok The answer is correct.
Test #75:
score: 0
Accepted
time: 0ms
memory: 5784kb
input:
14 24 3 0 31 31 23 9 15 21 25 21 25 27 27
output:
No
result:
ok The answer is correct.
Test #76:
score: 0
Accepted
time: 1ms
memory: 6008kb
input:
14 27 46 64 56 68 68 68 13 74 74 74 51 26 55
output:
No
result:
ok The answer is correct.
Subtask #4:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #77:
score: 0
Runtime Error
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%