QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#228645 | #3869. Gastronomic Event | ucup-team1004 | AC ✓ | 182ms | 74168kb | C++14 | 933b | 2023-10-28 13:52:16 | 2023-10-28 13:52:16 |
Judging History
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'