QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#331015#8225. 最小值之和djwj23339 609ms6136kbC++142.4kb2024-02-17 22:14:522024-02-17 22:14:52

Judging History

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

  • [2024-02-17 22:14:52]
  • 评测
  • 测评结果:39
  • 用时:609ms
  • 内存:6136kb
  • [2024-02-17 22:14:52]
  • 提交

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%