QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#228645#3869. Gastronomic Eventucup-team1004AC ✓182ms74168kbC++14933b2023-10-28 13:52:162023-10-28 13:52:16

Judging History

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

  • [2023-10-28 13:52:16]
  • 评测
  • 测评结果:AC
  • 用时:182ms
  • 内存:74168kb
  • [2023-10-28 13:52:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e6+10;
int n,siz[N],mx[N],cnt[N];
ll ans;
vector<int>to[N];
bitset<N>f;
void dfs1(int u,int fa=0){
	siz[u]=1;
	for(int v:to[u])if(v^fa){
		dfs1(v,u);
		mx[u]=max(mx[u],siz[v]);
		siz[u]+=siz[v];
	}
}
void dfs2(int u,int fa=0,int d=0){
	ans+=d,siz[u]=1;
	for(int v:to[u])if(v^fa){
		dfs2(v,u,d+1);
		siz[u]+=siz[v];
	}
}
int main(){
	scanf("%d",&n);
	for(int i=2,x;i<=n;i++){
		scanf("%d",&x);
		to[x].push_back(i),to[i].push_back(x);
	}
	dfs1(1);
	int rt=1;
	for(int i=1;i<=n;i++){
		mx[i]=max(mx[i],n-siz[i]),rt=mx[i]<mx[rt]?i:rt;
	}
	dfs2(rt);
	for(int v:to[rt])cnt[siz[v]]++;
	for(int i=1;i<=n;i++)for(;cnt[i]>2;cnt[i]-=2)cnt[i*2]++;
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=cnt[i];j++)f|=f<<i;
	}
	for(int i=(n-1)/2;~i;i--)if(f[i]){
		ans+=1ll*i*(n-1-i);break;
	}
	cout<<ans+n<<endl;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 5ms
memory: 31352kb

input:

5
1 2 2 2

output:

13

result:

ok single line: '13'

Test #2:

score: 0
Accepted
time: 3ms
memory: 30220kb

input:

10
1 2 3 4 3 2 7 8 7

output:

47

result:

ok single line: '47'

Test #3:

score: 0
Accepted
time: 145ms
memory: 70652kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 35 38 39 40 40 39 43 38 45 35 35 34 34 34 33 52 53 54 55 56 56 58 56 60 60 60 63 56 65 65 55 54 53 70 71 72 71 74 70 76 77 78 79 76 81 82 70 84 70 70 53 88 89 90 91 90 89 94 95 96 94 89 88 100 ...

output:

249834400049

result:

ok single line: '249834400049'

Test #4:

score: 0
Accepted
time: 109ms
memory: 72880kb

input:

1000000
1 2 3 4 5 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 ...

output:

250003506532

result:

ok single line: '250003506532'

Test #5:

score: 0
Accepted
time: 163ms
memory: 70076kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 27 31 31 33 34 35 36 37 38 39 40 41 42 43 43 45 46 47 48 49 50 51 52 53 54 53 52 57 58 59 59 57 62 63 64 65 66 67 65 63 70 70 63 73 73 62 76 76 78 79 62 81 82 83 62 85 86 85 88 85 52 91 51 93 94 51 96 97 98 99 100 ...

output:

249978362970

result:

ok single line: '249978362970'

Test #6:

score: 0
Accepted
time: 112ms
memory: 71756kb

input:

1000000
1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

250002449323

result:

ok single line: '250002449323'

Test #7:

score: 0
Accepted
time: 159ms
memory: 68752kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

250193522166

result:

ok single line: '250193522166'

Test #8:

score: 0
Accepted
time: 109ms
memory: 68912kb

input:

999997
1 2 3 3 2 6 6 2 9 9 2 12 13 2 15 15 2 18 19 2 21 22 2 24 25 2 27 28 2 30 31 2 33 33 2 36 37 2 39 40 2 42 43 2 45 45 2 48 48 2 51 52 2 54 55 2 57 57 2 60 61 2 63 63 2 66 66 2 69 69 2 72 72 2 75 76 2 78 78 2 81 81 2 84 84 2 87 87 2 90 91 2 93 94 2 96 97 2 99 99 2 102 103 2 105 106 2 108 108 2 1...

output:

250000666076

result:

ok single line: '250000666076'

Test #9:

score: 0
Accepted
time: 65ms
memory: 47576kb

input:

420001
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 26 30 31 32 31 30 35 26 26 38 25 40 41 42 43 43 43 42 41 48 49 48 25 52 53 54 54 53 57 58 58 52 25 62 63 25 65 66 67 66 65 65 71 24 73 74 75 76 77 77 76 75 81 75 83 84 85 83 74 88 88 90 74 92 74 74 73 96 97 96 73 100 1...

output:

44105186491

result:

ok single line: '44105186491'

Test #10:

score: 0
Accepted
time: 57ms
memory: 47792kb

input:

420121
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 29 34 27 36 37 36 39 40 27 42 27 26 45 45 47 48 49 48 47 52 53 45 55 56 57 58 59 57 61 62 57 57 56 56 67 68 67 56 26 72 25 74 75 76 77 77 77 76 81 76 75 84 85 75 75 74 89 25 91 92 92 94 94 91 25 98 99 98 10...

output:

44130371130

result:

ok single line: '44130371130'

Test #11:

score: 0
Accepted
time: 151ms
memory: 68944kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 22 22 20 25 26 27 28 29 30 28 32 32 28 28 36 27 38 39 39 38 38 38 26 26 46 47 47 26 25 51 52 53 53 52 56 57 58 56 52 61 62 62 64 65 66 67 66 65 62 71 71 71 71 62 76 77 78 78 77 81 76 83 83 76 86 52 51 51 51 51 92 92 20 95 96 97 96 99 96 1...

output:

250007600773

result:

ok single line: '250007600773'

Test #12:

score: 0
Accepted
time: 126ms
memory: 69752kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 22 23 24 25 26 27 26 29 29 25 24 33 34 35 36 37 34 39 40 34 42 33 44 24 46 24 48 24 22 51 52 53 54 55 56 56 53 52 60 61 61 63 60 65 66 65 68 52 51 51 22 73 73 75 73 73 22 79 80 81 79 79 84 20 86 87 88 89 90 89 19 93 94 95 95 97 94 99 93 1...

output:

250007340814

result:

ok single line: '250007340814'

Test #13:

score: 0
Accepted
time: 149ms
memory: 70992kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 25 28 28 30 30 28 33 25 24 36 37 37 39 37 41 42 37 36 45 46 47 46 45 50 45 52 24 54 23 56 57 58 59 60 61 62 62 62 61 60 59 68 68 59 71 71 58 74 74 76 58 57 79 80 81 81 83 80 85 80 87 88 89 89 80 80 79 79 57 56 56 98 99 100 9...

output:

250012392132

result:

ok single line: '250012392132'

Test #14:

score: 0
Accepted
time: 121ms
memory: 71180kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 12 11 11 11 17 11 19 11 21 11 11 11 11 11 11 11 11 10 31 32 32 32 32 32 32 31 39 31 41 31 43 31 45 31 31 31 31 31 31 31 31 31 31 31 31 10 59 59 59 59 63 59 59 59 59 59 59 59 10 72 73 73 72 72 72 72 72 72 72 72 72 10 85 85 85 85 85 85 10 92 93 94 93 93 93 93 93 93 92...

output:

250004726953

result:

ok single line: '250004726953'

Test #15:

score: 0
Accepted
time: 152ms
memory: 70252kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

245199646373

result:

ok single line: '245199646373'

Test #16:

score: 0
Accepted
time: 110ms
memory: 73552kb

input:

1000000
1 2 3 4 5 6 7 8 7 7 11 7 13 7 15 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7...

output:

250003475896

result:

ok single line: '250003475896'

Test #17:

score: 0
Accepted
time: 118ms
memory: 73424kb

input:

1000000
1 2 3 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 ...

output:

250002634697

result:

ok single line: '250002634697'

Test #18:

score: 0
Accepted
time: 97ms
memory: 72008kb

input:

1000000
1 2 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

250002449642

result:

ok single line: '250002449642'

Test #19:

score: 0
Accepted
time: 95ms
memory: 72312kb

input:

1000000
1 2 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:

250002222111

result:

ok single line: '250002222111'

Test #20:

score: 0
Accepted
time: 84ms
memory: 71684kb

input:

1000000
1 2 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:

250001648514

result:

ok single line: '250001648514'

Test #21:

score: 0
Accepted
time: 151ms
memory: 69204kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

250119221665

result:

ok single line: '250119221665'

Test #22:

score: 0
Accepted
time: 131ms
memory: 72552kb

input:

1000000
1 2 3 3 3 6 3 8 3 10 10 3 13 13 3 16 16 16 3 20 20 20 3 24 24 24 24 3 29 29 29 29 3 34 34 34 34 34 3 40 40 40 40 40 3 46 46 46 46 46 46 3 53 53 53 53 53 53 3 60 60 60 60 60 60 60 3 68 68 68 68 68 68 68 3 76 76 76 76 76 76 76 76 3 85 85 85 85 85 85 85 85 3 94 94 94 94 94 94 94 94 94 3 104 104...

output:

250002575077

result:

ok single line: '250002575077'

Test #23:

score: 0
Accepted
time: 0ms
memory: 30356kb

input:

2
1

output:

3

result:

ok single line: '3'

Test #24:

score: 0
Accepted
time: 146ms
memory: 67816kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

250318617239

result:

ok single line: '250318617239'

Test #25:

score: 0
Accepted
time: 133ms
memory: 72432kb

input:

1000000
1 2 3 3 3 6 3 8 3 10 10 3 13 13 3 16 16 16 3 20 20 20 3 24 24 24 24 3 29 29 29 29 3 34 34 34 34 34 3 40 40 40 40 40 3 46 46 46 46 46 46 3 53 53 53 53 53 53 3 60 60 60 60 60 60 60 3 68 68 68 68 68 68 68 3 76 76 76 76 76 76 76 76 3 85 85 85 85 85 85 85 85 3 94 94 94 94 94 94 94 94 94 3 104 104...

output:

250002497999

result:

ok single line: '250002497999'

Test #26:

score: 0
Accepted
time: 175ms
memory: 69720kb

input:

999999
1 2 3 4 5 6 7 8 9 10 10 10 13 10 15 10 17 17 10 20 20 10 23 24 23 10 27 27 29 10 31 32 33 33 10 36 37 36 36 10 41 42 43 41 45 10 47 48 47 50 47 10 53 54 54 56 56 53 10 60 61 62 62 61 65 10 67 68 68 67 71 67 73 10 75 76 77 78 78 80 76 10 83 84 85 84 87 84 89 83 10 92 93 92 95 95 97 98 92 10 10...

output:

250006990483

result:

ok single line: '250006990483'

Test #27:

score: 0
Accepted
time: 158ms
memory: 67048kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

250334332500

result:

ok single line: '250334332500'

Test #28:

score: 0
Accepted
time: 176ms
memory: 68200kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

output:

250079005570

result:

ok single line: '250079005570'

Test #29:

score: 0
Accepted
time: 182ms
memory: 68368kb

input:

1000000
1 2 3 4 5 6 6 8 6 10 10 6 13 14 13 6 17 17 19 17 6 22 22 24 22 26 6 28 29 29 29 28 33 6 35 36 37 37 36 40 35 6 43 44 43 46 43 43 49 43 6 52 53 54 54 56 54 53 52 60 6 62 63 63 63 62 62 62 69 62 62 6 73 74 75 76 76 75 74 80 74 73 83 6 85 86 87 87 87 87 86 92 93 86 86 85 6 98 98 100 100 102 103...

output:

250007833028

result:

ok single line: '250007833028'

Test #30:

score: 0
Accepted
time: 162ms
memory: 69448kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 11 13 11 15 16 11 18 19 18 11 22 23 22 22 11 27 28 28 30 31 11 33 34 35 35 33 33 11 40 41 42 40 44 45 45 11 48 49 49 49 52 49 48 48 11 57 58 59 59 58 57 63 63 57 11 67 68 68 67 67 72 73 74 73 76 11 78 79 80 81 80 80 79 79 79 78 88 11 90 91 91 90 90 95 96 97 90 90 100 ...

output:

250007840160

result:

ok single line: '250007840160'

Test #31:

score: 0
Accepted
time: 147ms
memory: 70836kb

input:

999999
1 2 3 4 4 6 4 8 8 4 11 11 11 4 15 16 16 15 4 20 21 20 20 20 4 26 27 26 26 26 26 4 33 33 33 33 33 33 33 4 41 42 42 41 45 41 47 41 4 50 51 50 50 54 50 50 50 50 4 60 61 61 61 61 60 60 60 60 60 4 71 72 72 72 71 76 71 78 71 71 71 4 83 84 84 84 84 83 83 83 83 83 83 83 4 96 97 97 97 97 96 96 96 104 ...

output:

250004116999

result:

ok single line: '250004116999'

Test #32:

score: 0
Accepted
time: 181ms
memory: 68484kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 75 77 75 79 80 75 82 83 84 75 86 87 88 89 75 91 92 93 94 95 75 97 98 99 100 1...

output:

250068466444

result:

ok single line: '250068466444'

Test #33:

score: 0
Accepted
time: 139ms
memory: 67172kb

input:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

250472199291

result:

ok single line: '250472199291'

Test #34:

score: 0
Accepted
time: 3ms
memory: 31392kb

input:

3
1 1

output:

6

result:

ok single line: '6'

Test #35:

score: 0
Accepted
time: 112ms
memory: 74108kb

input:

1000000
1 2 3 3 5 3 7 7 3 10 10 10 3 14 14 14 14 3 19 19 19 19 19 3 25 25 25 25 25 25 3 32 32 32 32 32 32 32 3 40 40 40 40 40 40 40 40 3 49 49 49 49 49 49 49 49 49 3 59 59 59 59 59 59 59 59 59 59 3 70 70 70 70 70 70 70 70 70 70 70 3 82 82 82 82 82 82 82 82 82 82 82 82 3 95 95 95 95 95 95 95 95 95 95...

output:

250002498584

result:

ok single line: '250002498584'

Test #36:

score: 0
Accepted
time: 125ms
memory: 73580kb

input:

1000000
1 2 3 3 5 3 7 7 3 10 10 10 3 14 14 14 14 3 19 19 19 19 19 3 25 25 25 25 25 25 3 32 32 32 32 32 32 32 3 40 40 40 40 40 40 40 40 3 49 49 49 49 49 49 49 49 49 3 59 59 59 59 59 59 59 59 59 59 3 70 70 70 70 70 70 70 70 70 70 70 3 82 82 82 82 82 82 82 82 82 82 82 82 3 95 95 95 95 95 95 95 95 95 95...

output:

250002498584

result:

ok single line: '250002498584'

Test #37:

score: 0
Accepted
time: 81ms
memory: 72912kb

input:

1000000
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

250001499999

result:

ok single line: '250001499999'

Test #38:

score: 0
Accepted
time: 133ms
memory: 73428kb

input:

1000000
1 2 3 4 4 4 7 4 9 4 11 11 4 14 14 4 17 17 17 4 21 21 21 4 25 25 25 25 4 30 30 30 30 4 35 35 35 35 35 4 41 41 41 41 41 4 47 47 47 47 47 47 4 54 54 54 54 54 54 4 61 61 61 61 61 61 61 4 69 69 69 69 69 69 69 4 77 77 77 77 77 77 77 77 4 86 86 86 86 86 86 86 86 4 95 95 95 95 95 95 95 95 95 4 105 1...

output:

250002575168

result:

ok single line: '250002575168'

Test #39:

score: 0
Accepted
time: 109ms
memory: 74168kb

input:

1000000
1 2 3 3 3 3 7 3 9 3 11 3 13 13 3 16 16 3 19 19 3 22 22 22 3 26 26 26 3 30 30 30 3 34 34 34 34 3 39 39 39 39 3 44 44 44 44 3 49 49 49 49 49 3 55 55 55 55 55 3 61 61 61 61 61 3 67 67 67 67 67 67 3 74 74 74 74 74 74 3 81 81 81 81 81 81 3 88 88 88 88 88 88 88 3 96 96 96 96 96 96 96 3 104 104 104...

output:

250002497550

result:

ok single line: '250002497550'

Test #40:

score: 0
Accepted
time: 131ms
memory: 72936kb

input:

1000000
1 2 3 3 3 3 3 8 3 10 3 12 3 14 3 16 16 3 19 19 3 22 22 3 25 25 3 28 28 28 3 32 32 32 3 36 36 36 3 40 40 40 3 44 44 44 44 3 49 49 49 49 3 54 54 54 54 3 59 59 59 59 3 64 64 64 64 64 3 70 70 70 70 70 3 76 76 76 76 76 3 82 82 82 82 82 3 88 88 88 88 88 88 3 95 95 95 95 95 95 3 102 102 102 102 102...

output:

250002497171

result:

ok single line: '250002497171'

Test #41:

score: 0
Accepted
time: 136ms
memory: 70604kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 36 38 39 40 39 35 43 33 45 45 47 48 49 50 51 50 49 49 55 47 33 58 59 60 59 58 33 64 65 66 67 33 69 70 70 72 73 72 72 76 72 78 33 80 81 80 83 84 84 84 83 88 88 90 33 92 93 94 95 95 97 95 33 100 1...

output:

250020676589

result:

ok single line: '250020676589'

Test #42:

score: 0
Accepted
time: 128ms
memory: 69472kb

input:

999999
1 2 3 4 5 3 7 3 9 10 11 11 3 14 14 3 17 18 19 20 3 22 23 24 3 26 27 3 29 3 31 32 33 3 35 36 37 37 3 40 41 3 43 43 45 3 47 48 3 50 3 52 3 54 55 55 57 3 59 60 3 62 3 64 65 3 67 3 69 70 3 72 73 73 3 76 3 78 79 80 3 82 83 3 85 86 87 3 89 90 91 3 93 94 95 96 3 98 3 100 101 3 103 104 3 106 107 107 ...

output:

250019615929

result:

ok single line: '250019615929'

Test #43:

score: 0
Accepted
time: 127ms
memory: 70948kb

input:

999999
1 2 3 4 5 3 7 8 3 10 3 12 13 3 15 3 17 3 19 20 3 22 23 3 25 26 3 28 29 3 31 3 33 34 3 36 3 38 3 40 41 3 43 3 45 46 3 48 3 50 3 52 3 54 55 3 57 3 59 60 3 62 62 3 65 66 3 68 3 70 3 72 73 3 75 76 3 78 3 80 3 82 83 3 85 3 87 88 3 90 91 3 93 94 3 96 3 98 3 100 100 3 103 104 3 106 107 3 109 110 3 1...

output:

250018067270

result:

ok single line: '250018067270'

Test #44:

score: 0
Accepted
time: 123ms
memory: 70872kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 33 36 33 38 33 40 33 42 33 44 33 46 33 48 33 50 33 52 33 54 33 56 33 58 33 60 33 62 33 64 33 66 33 68 33 70 33 72 33 74 33 76 33 78 33 80 33 82 33 84 33 86 33 88 33 90 33 92 33 94 33 96 33 98 33 100 3...

output:

250017908559

result:

ok single line: '250017908559'

Test #45:

score: 0
Accepted
time: 7ms
memory: 31508kb

input:

13
1 2 3 3 2 6 6 2 9 2 11 1

output:

68

result:

ok single line: '68'

Test #46:

score: 0
Accepted
time: 137ms
memory: 69488kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 33 33 33 31 29 43 44 44 44 47 48 49 50 29 52 53 29 55 56 57 58 59 58 61 61 63 64 56 29 67 68 69 70 71 71 73 70 75 70 77 78 79 67 29 82 83 84 85 86 87 88 89 90 90 89 87 94 94 86 97 82 29 100 1...

output:

250026260338

result:

ok single line: '250026260338'

Test #47:

score: 0
Accepted
time: 145ms
memory: 68848kb

input:

999999
1 2 3 4 5 6 2 8 9 9 9 2 13 14 13 2 17 18 19 2 21 21 23 2 25 2 27 2 29 30 31 30 2 34 35 36 37 2 39 2 41 42 43 44 2 46 47 48 2 50 51 52 2 54 2 56 57 58 58 2 61 62 63 64 2 66 2 68 69 70 2 72 73 2 75 76 2 78 2 80 81 2 83 84 2 86 2 88 89 89 2 92 92 2 95 2 97 98 97 100 2 102 103 2 105 2 107 108 2 1...

output:

250026892857

result:

ok single line: '250026892857'

Test #48:

score: 0
Accepted
time: 131ms
memory: 69376kb

input:

999999
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 31 34 31 36 31 38 39 31 41 41 31 44 31 46 31 48 31 50 31 52 53 31 55 31 57 31 59 31 61 62 31 64 65 31 67 31 69 70 31 72 31 74 31 76 31 78 31 80 31 82 83 31 85 86 31 88 89 31 91 31 93 31 95 96 31 98 31 100 3...

output:

250026401059

result:

ok single line: '250026401059'

Test #49:

score: 0
Accepted
time: 3ms
memory: 29936kb

input:

100
1 2 3 4 5 6 7 7 9 10 11 9 13 6 5 16 5 18 19 20 20 22 19 24 19 26 19 19 18 5 4 32 33 32 4 36 37 37 39 4 3 3 43 44 2 46 47 48 49 50 51 52 51 54 54 54 50 58 50 50 61 48 63 63 47 66 47 68 69 70 70 72 68 47 47 46 77 46 2 80 80 2 83 84 85 86 87 85 89 84 91 91 91 94 84 84 84 2 2

output:

3002

result:

ok single line: '3002'

Test #50:

score: 0
Accepted
time: 0ms
memory: 30132kb

input:

100
1 2 3 4 5 5 5 4 9 9 9 4 13 13 4 4 17 4 4 4 4 4 4 4 4 3 27 28 27 27 27 27 27 27 27 27 27 27 3 40 40 40 40 40 40 3 47 47 3 50 50 50 3 54 54 54 3 58 58 58 58 3 3 64 3 66 3 68 68 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 91 2 2 2 2 2 2 2 2

output:

2732

result:

ok single line: '2732'

Test #51:

score: 0
Accepted
time: 0ms
memory: 30188kb

input:

100
1 2 3 4 5 6 7 8 4 10 11 12 13 14 15 16 17 18 19 20 20 17 23 23 25 26 27 28 29 27 31 32 33 33 35 36 37 36 39 40 41 41 43 43 41 46 40 48 49 50 51 51 48 54 55 55 57 58 48 60 61 62 62 64 65 60 67 68 60 36 35 72 73 74 75 76 76 78 79 80 78 82 83 84 85 75 75 88 73 72 32 92 31 25 95 14 14 14 2

output:

3283

result:

ok single line: '3283'

Test #52:

score: 0
Accepted
time: 0ms
memory: 30332kb

input:

421
1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 16 17 17 19 19 21 22 23 24 25 26 27 27 29 24 23 32 33 34 35 34 37 38 39 40 41 42 43 43 45 46 45 48 42 41 51 51 51 41 39 56 56 56 37 60 61 62 63 62 61 66 37 68 68 33 19 16 3 74 75 76 77 77 79 80 81 82 83 84 85 86 86 88 89 90 89 92 93 94 95 96 96 98 99 94 101 10...

output:

51047

result:

ok single line: '51047'