QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#408677	#8225. 最小值之和	xuqin	36	319ms	8768kb	C++14	2.1kb	2024-05-10 21:11:41	2024-05-10 21:11:42

Judging History

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

[2024-05-10 21:11:42]
评测

测评结果：36
用时：319ms
内存：8768kb

查看

[2024-05-10 21:11:41]
提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cassert>
#include<set>
#include<random>
#include<chrono>
#include<bitset>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#define eb emplace_back

using namespace std;
const int maxn=(1<<18)+10, maxm=11+10, inf=2e9+10, P=1e9+7;
const double eps=1e-10, pi=acos(-1.0);
typedef long long LL;
typedef unsigned long long ULL;
const LL INF=4e18;
typedef pair<LL, int> pli;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, LL> pll;
inline int read() {
	int x=0, f=1; char c=getchar();
	for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=0;
	for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
	return f?x:-x;
}
mt19937 rnd((unsigned)chrono::steady_clock::now().time_since_epoch().count());
inline int ksm(int x, int y) {
	int s=1;
	for(; y; y>>=1, x=1LL*x*x%P)
		if(y&1) s=1LL*s*x%P;
	return s;
}
inline int add(int x, int y) {x+=y; return x>=P?x-P:x;}
inline int del(int x, int y) {x-=y; return x<0?x+P:x;}
LL gcd(LL x, LL y) {return y?gcd(y, x%y):x;}

int dp[60][60][2510];
pii cho[60][60][2510];
int a[60], f[60];

void dfs(int l, int r, int k) {
	if(l==r+1) return;
	int p, c;
	tie(p, c)=cho[l][r][k];
	for(int i=l; i<=r; ++i) a[i]+=c;
	dfs(l, p-1, k+(r-l+1)*c); dfs(p+1, r, k+(r-l+1)*c);
}

int main() {
	int n=read(), fl=0;
	for(int i=1; i<=n; ++i) f[i]=read(), fl|=(f[i]>2401);
	if(fl) return puts("No"), 0;
	for(int i=1; i<=n; ++i) dp[i][i-1][f[i]]=1;
	for(int len=1; len<=n-1; ++len) {
		for(int l=1; l+len-1<=n-1; ++l) {
			int r=l+len-1, mx=0;
			for(int i=l; i<=r+1; ++i) mx=max(mx, f[i]);
			for(int k=0; k<=mx; ++k) {
				for(int p=l; p<=r; ++p) 
					for(int c=0; c<50&&k+(r-l+1)*c<=2500; ++c) {
						if(dp[l][p-1][k+(r-l+1)*c]&&dp[p+1][r][k+(r-l+1)*c]) {
							dp[l][r][k]=1;
							cho[l][r][k]=make_pair(p, c);
						} 
					}
			}
		}
	}
	if(dp[1][n-1][0]==0) return puts("No"), 0;
	puts("Yes");
	dfs(1, n-1, 0);
	for(int i=1; i<n; ++i) printf("%d ", a[i]);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11

Accepted

Test #1:

score: 11

Accepted

time: 1ms

memory: 3908kb

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4

result:

ok The answer is correct.

Test #2:

score: 11

Accepted

time: 1ms

memory: 3840kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1

result:

ok The answer is correct.

Test #3:

score: 11

Accepted

time: 1ms

memory: 3820kb

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: 1ms

memory: 3760kb

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2

result:

ok The answer is correct.

Test #5:

score: 11

Accepted

time: 1ms

memory: 3836kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1

result:

ok The answer is correct.

Test #6:

score: 11

Accepted

time: 0ms

memory: 3764kb

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: 3920kb

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8

result:

ok The answer is correct.

Test #8:

score: 11

Accepted

time: 0ms

memory: 3756kb

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: 3900kb

input:

5
10 10 8 5 5

output:

Yes
5 3 1 2

result:

ok The answer is correct.

Test #10:

score: 11

Accepted

time: 0ms

memory: 3824kb

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7

result:

ok The answer is correct.

Test #11:

score: 11

Accepted

time: 1ms

memory: 3792kb

input:

5
5 5 22 31 31

output:

Yes
2 1 10 19

result:

ok The answer is correct.

Test #12:

score: 11

Accepted

time: 0ms

memory: 3764kb

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: 3804kb

input:

5
16 16 4 12 12

output:

Yes
13 1 1 9

result:

ok The answer is correct.

Test #14:

score: 11

Accepted

time: 0ms

memory: 3852kb

input:

5
29 29 24 26 26

output:

Yes
11 6 6 8

result:

ok The answer is correct.

Test #15:

score: 11

Accepted

time: 0ms

memory: 3868kb

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: 3696kb

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

score: 11

Accepted

time: 0ms

memory: 3524kb

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

score: 11

Accepted

time: 0ms

memory: 3768kb

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

score: 11

Accepted

time: 0ms

memory: 3608kb

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

score: 11

Accepted

time: 1ms

memory: 3692kb

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

score: 11

Accepted

time: 0ms

memory: 3728kb

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

score: 11

Accepted

time: 0ms

memory: 3796kb

input:

5
6 7 7 6 6

output:

Yes
2 3 1 3

result:

ok The answer is correct.

Test #23:

score: 11

Accepted

time: 1ms

memory: 3908kb

input:

5
25 25 24 20 20

output:

Yes
8 7 5 5

result:

ok The answer is correct.

Test #24:

score: 11

Accepted

time: 0ms

memory: 3684kb

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

score: 11

Accepted

time: 0ms

memory: 3608kb

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

score: 11

Accepted

time: 0ms

memory: 3520kb

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

score: 11

Accepted

time: 0ms

memory: 3748kb

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

score: 11

Accepted

time: 0ms

memory: 3484kb

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

score: 11

Accepted

time: 0ms

memory: 3688kb

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

score: 11

Accepted

time: 1ms

memory: 3684kb

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

score: 11

Accepted

time: 0ms

memory: 3460kb

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

score: 11

Accepted

time: 0ms

memory: 3692kb

input:

2
2 2

output:

Yes
2

result:

ok The answer is correct.

Test #33:

score: 11

Accepted

time: 1ms

memory: 3652kb

input:

1
0

output:

Yes

result:

ok The answer is correct.

Test #34:

score: 11

Accepted

time: 0ms

memory: 3664kb

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: 4036kb

input:

8
16 16 8 8 9 9 6 6

output:

Yes
10 2 2 1 5 0 6

result:

ok The answer is correct.

Test #36:

score: 15

Accepted

time: 1ms

memory: 3896kb

input:

8
16 16 9 21 21 23 23 23

output:

Yes
9 2 1 15 1 9 9

result:

ok The answer is correct.

Test #37:

score: 15

Accepted

time: 1ms

memory: 3908kb

input:

8
10 10 15 15 15 10 10 5

output:

Yes
10 0 5 5 2 3 1

result:

ok The answer is correct.

Test #38:

score: 15

Accepted

time: 1ms

memory: 3880kb

input:

8
13 13 15 15 24 24 24 10

output:

Yes
3 3 5 1 9 9 2

result:

ok The answer is correct.

Test #39:

score: 15

Accepted

time: 1ms

memory: 3984kb

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: 2ms

memory: 3768kb

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

No

result:

wrong answer Line 1 expected

Subtask #3:

score: 0

Skipped

Dependency #2:

Subtask #4:

score: 25

Accepted

Dependency #1:

100%

Accepted

Test #77:

score: 25

Accepted

time: 28ms

memory: 6504kb

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
4 4 2 1 11 7 1 12 5 1 23 1 21 1 3 10 13 8 1 15 16 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: 49ms

memory: 8296kb

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
1 1 27 0 31 0 34 0 14 11 3 7 6 0 21 0 16 5 9 12 11 0 22 0 6 0 4 10 24 30 1 36 37 0 55 21 0 26 20 0 30 30 0 30 30 0 4 2

result:

ok The answer is correct.

Test #79:

score: 25

Accepted

time: 61ms

memory: 7472kb

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
3 3 1 3 1 16 17 20 1 44 1 23 22 23 0 36 47 1 28 25 21 3 8 15 14 12 0 18 16 9 12 4 7 6 1 0 13 0 10 7 0 8 11 0 13 0 9 9

result:

ok The answer is correct.

Test #80:

score: 25

Accepted

time: 49ms

memory: 8768kb

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
5 9 1 5 4 1 9 3 7 10 9 1 24 1 33 1 20 15 1 18 17 1 37 1 42 1 42 1 42 1 14 1 14 1 2 0 31 2 0 8 0 6 0 11 0 3 0 5 5

result:

ok The answer is correct.

Test #81:

score: 25

Accepted

time: 30ms

memory: 7880kb

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
2 4 1 7 1 1 5 19 1 21 0 0 0 3 2 0 0 9 0 5 5 1 4 7 9 6 6 5 3 0 13 14 0 6 0 5 2 5 7 6 0 3 26 3 25 3 10 8

result:

ok The answer is correct.

Test #82:

score: 25

Accepted

time: 26ms

memory: 6268kb

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 7 4 3 5 6 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: 190ms

memory: 6072kb

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 23 13 14 7 37 25 26 25 33 9 0 13 4 58 35 6 10 26 43 26 51 35 22 19 25 18 9 5 16 20 22 3 51 34 0 33 31 44 0 54 27 9 39 12

result:

ok The answer is correct.

Test #84:

score: 25

Accepted

time: 285ms

memory: 8132kb

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
7 34 34 66 34 61 46 32 34 3 78 37 38 36 48 8 84 61 60 11 2 27 28 29 49 47 29 53 15 33 2 27 75 84 69 2 77 76 45 47 2 47 69 1 19 1 31 1 37

result:

ok The answer is correct.

Test #85:

score: 25

Accepted

time: 185ms

memory: 7324kb

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
11 35 11 10 49 41 8 31 46 6 36 17 11 7 15 4 38 38 20 18 19 22 11 3 2 21 16 16 31 53 2 57 51 53 2 21 19 40 2 38 40 30 26 26 30 0 22

result:

ok The answer is correct.

Test #86:

score: 25

Accepted

time: 319ms

memory: 6808kb

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
35 25 14 16 5 5 12 27 27 29 29 3 10 37 22 29 45 53 45 46 6 53 81 3 30 48 9 37 11 40 39 45 44 34 38 47 51 45 19 4 2 13 21 46 13 45 34 19

result:

ok The answer is correct.

Test #87:

score: 25

Accepted

time: 282ms

memory: 7116kb

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
46 30 8 40 38 37 34 45 44 41 9 7 19 46 7 28 2 25 23 19 29 20 34 43 34 22 18 43 38 49 39 2 73 83 57 85 8 60 75 42 45 30 78 35 11 2 15 17

result:

ok The answer is correct.

Test #88:

score: 25

Accepted

time: 236ms

memory: 7288kb

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
7 6 34 28 30 23 6 22 48 46 49 32 20 48 6 81 35 36 3 8 14 3 14 4 22 27 9 7 4 8 25 32 42 36 21 3 33 29 24 25 3 47 50 33 28 26 42

result:

ok The answer is correct.

Test #89:

score: 25

Accepted

time: 245ms

memory: 4108kb

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: 43ms

memory: 4432kb

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: 46ms

memory: 4732kb

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: 40ms

memory: 7328kb

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
6 3 2 21 0 19 9 0 12 9 8 0 11 10 8 1 8 0 0 0 0 23 19 0 38 0 37 0 27 0 13 47 0 34 36 0 23 22 26 0 43 24 0 49 0 25 22

result:

ok The answer is correct.

Test #93:

score: 25

Accepted

time: 32ms

memory: 5760kb

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: 47ms

memory: 5956kb

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: 30ms

memory: 7176kb

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: 36ms

memory: 5604kb

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:

Subtask #6:

score: 0

Skipped

Dependency #1:

100%

Accepted