QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#331013 | #8225. 最小值之和 | djwj233 | 11 | 14ms | 6132kb | C++14 | 2.4kb | 2024-02-17 22:13:51 | 2024-02-17 22:13:51 |
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: 5944kb
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: 6084kb
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: 6064kb
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: 6064kb
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: 1ms
memory: 6120kb
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: 0ms
memory: 6004kb
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: 0ms
memory: 6096kb
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: 6088kb
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: 1ms
memory: 6128kb
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: 0ms
memory: 6068kb
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: 1ms
memory: 6084kb
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: 6088kb
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: 0ms
memory: 6088kb
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: 1ms
memory: 6072kb
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: 6024kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 1ms
memory: 5820kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 0ms
memory: 5956kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 0ms
memory: 5820kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 1ms
memory: 6072kb
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: 0ms
memory: 6132kb
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: 6020kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 1ms
memory: 5816kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 5800kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 0ms
memory: 5996kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 1ms
memory: 5960kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 1ms
memory: 5880kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 0ms
memory: 5816kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 0ms
memory: 6092kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3860kb
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: 0ms
memory: 6088kb
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: 1ms
memory: 6072kb
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
Wrong Answer
time: 1ms
memory: 5804kb
input:
8 10 10 15 15 15 10 10 5
output:
No
result:
wrong answer Line 1 expected
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #77:
score: 25
Accepted
time: 14ms
memory: 5944kb
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 6 13 16 11 1 21 22 1 1 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
Time Limit Exceeded
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%