QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#408616#8225. 最小值之和xuqin11 1ms3932kbC++142.0kb2024-05-10 20:07:232024-05-10 20:07:23

Judging History

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

  • [2024-05-10 20:07:23]
  • 评测
  • 测评结果:11
  • 用时:1ms
  • 内存:3932kb
  • [2024-05-10 20:07:23]
  • 提交

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][60];
pii cho[60][60][60];
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]>50);
	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;
			for(int k=0; k<=50; ++k) {
				for(int p=l; p<=r; ++p) 
					for(int c=0; c<=50; ++c) {
						if(k+(r-l+1)*c<=50&&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;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 1ms
memory: 3780kb

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: 0ms
memory: 3848kb

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: 0ms
memory: 3744kb

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: 0ms
memory: 3740kb

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

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

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

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: 1ms
memory: 3888kb

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: 1ms
memory: 3884kb

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

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: 0ms
memory: 3884kb

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: 1ms
memory: 3740kb

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

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

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: 1ms
memory: 3724kb

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: 1ms
memory: 3748kb

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

score: 11
Accepted
time: 1ms
memory: 3676kb

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

score: 11
Accepted
time: 1ms
memory: 3596kb

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

score: 11
Accepted
time: 0ms
memory: 3480kb

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

score: 11
Accepted
time: 1ms
memory: 3492kb

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

score: 11
Accepted
time: 0ms
memory: 3688kb

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

score: 11
Accepted
time: 1ms
memory: 3732kb

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: 0ms
memory: 3884kb

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

score: 11
Accepted
time: 1ms
memory: 3596kb

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

score: 11
Accepted
time: 1ms
memory: 3680kb

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

score: 11
Accepted
time: 0ms
memory: 3612kb

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

score: 11
Accepted
time: 0ms
memory: 3676kb

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

score: 11
Accepted
time: 0ms
memory: 3524kb

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

score: 11
Accepted
time: 0ms
memory: 3576kb

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

score: 11
Accepted
time: 0ms
memory: 3676kb

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

score: 11
Accepted
time: 0ms
memory: 3884kb

input:

2
2 2

output:

Yes
2 

result:

ok The answer is correct.

Test #33:

score: 11
Accepted
time: 1ms
memory: 3712kb

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: 0ms
memory: 3932kb

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

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

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

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

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: 0ms
memory: 3644kb

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

No

result:

wrong answer Line 1 expected @\x02\x12

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #77:

score: 0
Wrong Answer
time: 0ms
memory: 3656kb

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:

No

result:

wrong answer Line 1 expected 

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

0%