QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331013#8225. 最小值之和djwj23311 14ms6132kbC++142.4kb2024-02-17 22:13:512024-02-17 22:13:51

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 22:13:51]
  • 评测
  • 测评结果:11
  • 用时:14ms
  • 内存:6132kb
  • [2024-02-17 22:13:51]
  • 提交

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%