QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#110832 | #3869. Gastronomic Event | gigabuffoon | AC ✓ | 1833ms | 31140kb | C++20 | 2.2kb | 2023-06-04 02:54:41 | 2023-06-04 02:54:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(a, b, c) for (int a = (b); a < (c); a++)
#define sz(x) int(size(x))
#define all(x) begin(x), end(x)
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
void solve() {
int n;
cin >> n;
vi p(n, -1);
rep (i, 1, n) cin >> p[i], p[i]--;
vi sub(n, 1), big(n);
for (int i = n-1; i > 0; i--) {
if (i > 0) {
sub[p[i]] += sub[i];
big[p[i]] = max(big[p[i]], sub[i]);
}
big[i] = max(big[i], n - sub[i]);
}
int rt = min_element(all(big)) - begin(big);
vi num(n+1);
int cap = min(n / 2, n - 1 - big[rt]) + 1;
ll ans = big[rt] * ll(n - 1 - big[rt]);
rep (i, 0, n) if (p[i] == rt) {
int k = sub[i];
num[k]++;
}
if (n - sub[rt] > 0) {
int k = n - sub[rt];
num[k]++;
}
{
vector<bool> dp(1);
dp[0] = 1;
for (int k = 1; k <= n; k++) if (num[k]) {
int old = sz(dp);
auto next = dp;
next.resize(sz(dp) + num[k]*k);
vi on(k);
for (int j = 0, p = 0; p < sz(next); j++) {
for (int i = 0; i < k && p < sz(next); i++, p++) {
if (on[i]) next[p] = 1;
if (p < sz(dp)) on[i] += dp[p];
if (p >= num[k]*k) on[i] -= dp[p - num[k]*k];
}
}
swap(dp, next);
}
rep (i, 0, sz(dp)) if (dp[i]) ans = max(ans, i * ll(n - 1 - i));
}
vi down(n, -1);
for (int x = rt, y = p[x]; x != 0; x = y, y = p[x]) {
down[y] = x;
p[x] = -1;
}
vector<ll> dp(n, 1);
for (int i = n-1; i >= 0; i--) {
if (p[i] != -1)
dp[p[i]] += dp[i];
if (down[i] == -1 && i != rt) ans += dp[i];
}
for (int i = 0; i < n; i++) {
if (down[i] != -1) {
dp[down[i]] += dp[i];
ans += dp[i];
}
}
ans += dp[rt];
cout << ans << "\n";
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
// int t; cin >> t; while (t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3364kb
input:
5 1 2 2 2
output:
13
result:
ok single line: '13'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3368kb
input:
10 1 2 3 4 3 2 7 8 7
output:
47
result:
ok single line: '47'
Test #3:
score: 0
Accepted
time: 82ms
memory: 30632kb
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: 213ms
memory: 30900kb
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: 102ms
memory: 30656kb
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: 330ms
memory: 30612kb
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: 78ms
memory: 30628kb
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: 73ms
memory: 30448kb
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: 43ms
memory: 14608kb
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: 26ms
memory: 14612kb
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: 75ms
memory: 30540kb
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: 344ms
memory: 30620kb
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: 98ms
memory: 30744kb
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: 116ms
memory: 31140kb
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: 77ms
memory: 30692kb
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: 229ms
memory: 30604kb
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: 892ms
memory: 30544kb
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: 334ms
memory: 30604kb
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: 161ms
memory: 30872kb
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: 122ms
memory: 30856kb
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: 96ms
memory: 30684kb
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: 1300ms
memory: 30620kb
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: 2ms
memory: 3372kb
input:
2 1
output:
3
result:
ok single line: '3'
Test #24:
score: 0
Accepted
time: 1321ms
memory: 30528kb
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: 1338ms
memory: 30520kb
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: 1283ms
memory: 30524kb
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: 1304ms
memory: 30524kb
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: 1766ms
memory: 30552kb
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: 1777ms
memory: 30552kb
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: 1804ms
memory: 30552kb
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: 1792ms
memory: 30540kb
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: 1833ms
memory: 30528kb
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: 1810ms
memory: 30528kb
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: 2ms
memory: 3448kb
input:
3 1 1
output:
6
result:
ok single line: '6'
Test #35:
score: 0
Accepted
time: 1791ms
memory: 30616kb
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: 1815ms
memory: 30632kb
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: 73ms
memory: 30476kb
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: 1298ms
memory: 30512kb
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: 1063ms
memory: 30612kb
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: 959ms
memory: 30684kb
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: 92ms
memory: 30708kb
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: 96ms
memory: 30756kb
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: 100ms
memory: 30804kb
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: 89ms
memory: 30876kb
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: 2ms
memory: 3492kb
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: 78ms
memory: 30596kb
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: 103ms
memory: 30608kb
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: 82ms
memory: 30700kb
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: 1ms
memory: 3428kb
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: 2ms
memory: 3376kb
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: 2ms
memory: 3440kb
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: 2ms
memory: 3396kb
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'