QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#429990#7793. 雷同kkkgjyismine420 3ms10504kbC++14996b2024-06-03 09:31:222024-06-03 09:31:23

Judging History

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

  • [2024-06-03 09:31:23]
  • 评测
  • 测评结果:20
  • 用时:3ms
  • 内存:10504kb
  • [2024-06-03 09:31:22]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1e18;
int n;ll w[500050];
int g[500050];
ll f[103][103][103],sum[103];
void cmin(ll &x,const ll y){x=min(x,y);}
void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%lld",&w[i]);
	sort(w+1,w+n+1);
	for(int i=1;i<=n;++i)
	 for(int j=i;j<=n;++j)
	   for(int k=0;k<=n;++k)f[i][j][k]=inf;
	for(int i=1;i<=n;++i)f[i][i][0]=0,sum[i]=sum[i-1]+w[i];
	for(int i=n-1;i>=1;--i)
	    for(int j=i+1;j<=n;++j)
	        for(int k=i;k<j;++k)
	          for(int lef=g[k-i+1];lef<=g[k-i+1]+2&&lef<=k-i+1;++lef)
	            for(int rig=g[j-k];rig<=g[j-k]+2&&rig<=j-k;++rig)
	                cmin(f[i][j][max(lef,rig)+1],f[i][k][lef]+f[k+1][j][rig]+sum[j]-sum[i-1]+(1ll<<min(lef,rig))-1ll);
	ll ans=inf;
	for(int i=0;i<=n;++i)cmin(ans,f[1][n][i]);
	printf("%lld\n",ans);
}
int main(){
	g[1]=0;
	for(int i=2;i<=500000;++i)g[i]=max(g[i/2],g[i-i/2])+1;
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 2ms
memory: 8044kb

input:

4
6
1 3 5 7 9 11
6
2 4 6 8 10 12
6
100 1000 100 10 100 10
2
114514 1919810

output:

86
103
1981
2034324

result:

ok 4 tokens

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #2:

score: 15
Accepted
time: 0ms
memory: 10060kb

input:

5
12
2 4 3 2 2 3 4 2 3 2 2 1
12
3 3 3 2 3 2 3 2 1 1 2 4
12
6 2 2 2 5 4 6 1 2 8 8 6
12
1 4 2 2 1 6 7 2 4 1 7 5
12
11 1 2 6 16 16 15 8 8 16 6 12

output:

114
109
183
146
400

result:

ok 5 tokens

Test #3:

score: 15
Accepted
time: 2ms
memory: 7992kb

input:

5
12
4 2 4 3 2 4 4 4 3 1 1 1
12
3 4 6 5 2 3 2 5 1 3 4 4
12
3 6 4 3 5 2 5 2 5 2 3 1
12
1 2 2 3 7 7 6 4 1 2 9 3
12
12 5 12 4 3 9 3 14 5 11 6 6

output:

120
154
150
162
316

result:

ok 5 tokens

Test #4:

score: 15
Accepted
time: 2ms
memory: 8180kb

input:

5
12
3 1 2 1 2 3 1 1 1 2 1 3
12
4 7 7 6 6 2 3 7 1 7 6 6
12
13 7 13 7 9 1 5 13 3 13 9 7
12
12 12 15 13 15 22 33 33 21 9 15 3
12
123141171 193440418 455041175 665153544 746164805 372591232 659412139 493891488 760749047 4896558 90497398 964891156

output:

80
223
349
708
18084123310

result:

ok 5 tokens

Test #5:

score: 15
Accepted
time: 2ms
memory: 8076kb

input:

5
12
2 4 3 2 5 1 6 2 5 2 1 4
12
2 6 6 6 12 8 8 6 12 6 10 11
12
23 26 26 31 13 20 13 31 2 1 15 30
12
56 33 66 31 27 64 26 2 48 55 46 66
12
113216 35921 62630 73720 41172 102245 41642 39101 40760 105980 2857 63443

output:

133
335
782
1809
2470930

result:

ok 5 tokens

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #6:

score: 0
Wrong Answer
time: 3ms
memory: 10504kb

input:

5
30
34 3 20 7 6 9 22 3 24 2 3 40 25 9 6 4 3 36 5 38 21 9 5 4 21 6 28 32 17 3
30
1 6 9 2 6 9 7 2 2 4 3 5 6 8 9 7 2 7 12 7 8 4 9 8 2 8 2 12 3 2
30
4 1 1 4 4 1 3 4 3 2 4 4 1 1 2 3 3 3 2 1 2 4 4 3 3 4 4 4 3 1
30
9 6 9 8 3 10 10 1 6 1 1 6 6 10 4 9 1 4 1 6 1 10 4 9 10 7 5 2 9 8
28
7 9 6 3 5 5 1 10 9 3 1 ...

output:

2019
846
434
855
680

result:

wrong answer 4th words differ - expected: '854', found: '855'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Runtime Error

Test #39:

score: 0
Runtime Error

input:

2
2500
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...

output:


result:


Subtask #7:

score: 0
Skipped

Dependency #5:

0%