QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#407719 | #6538. Lonely King | xuqin | AC ✓ | 98ms | 26116kb | C++14 | 6.5kb | 2024-05-09 10:05:36 | 2024-05-09 10:05:38 |
Judging History
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=2e5+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<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;}
struct pj{
int lc, rc, sz; LL ad;
LL x, y;
} tr[maxn]; int cnt;
inline void update(int u) {
tr[u].sz=tr[tr[u].lc].sz+tr[tr[u].rc].sz+1;
}
inline int cmp(int x, int y) { //key(x)>key(y)
return rnd()%(tr[x].sz+tr[y].sz)<tr[x].sz;
}
inline int add_n(LL x, LL y) {
int u=++cnt;
tr[u].x=x; tr[u].y=y; tr[u].sz=1;
return u;
}
inline void pushdown(int u) {
if(tr[u].ad==0) return;
if(tr[u].lc) tr[tr[u].lc].y+=tr[u].ad, tr[tr[u].lc].ad+=tr[u].ad;
if(tr[u].rc) tr[tr[u].rc].y+=tr[u].ad, tr[tr[u].rc].ad+=tr[u].ad;
tr[u].ad=0;
}
void splitrk(int u, int rk, int& x, int& y) {//x:<=rk y:>rk
if(u==0) {x=y=0; return;}
pushdown(u);
if(tr[tr[u].lc].sz+1<=rk) {
x=u; splitrk(tr[u].rc, rk-(tr[tr[u].lc].sz+1), tr[x].rc, y);
update(x);
} else {
y=u; splitrk(tr[u].lc, rk, x, tr[y].lc);
update(y);
}
}
void splitval(int u, LL val, int& x, int& y) {//x:<=val y:>val
if(u==0) {x=y=0; return;}
pushdown(u);
if(tr[u].x<=val) {
x=u; splitval(tr[u].rc, val, tr[x].rc, y);
update(x);
} else {
y=u; splitval(tr[u].lc, val, x, tr[y].lc);
update(y);
}
}
int merge(int x, int y) {
if(x==0||y==0) return x^y;
int u;
pushdown(x); pushdown(y);
if(cmp(x, y)) u=x, tr[u].rc=merge(tr[x].rc, y);
else u=y, tr[u].lc=merge(x, tr[y].lc);
update(u);
return u;
}
struct tg{int y, nxt;} g[maxn];
int len, la[maxn];
inline void add_e(int x, int y) {g[++len].y=y; g[len].nxt=la[x]; la[x]=len;}
LL f[maxn], c[maxn];
int rt[maxn], sz[maxn], lst[maxn], tot;
void getlst(int x) {
// assert(x>0);
pushdown(x);
if(tr[x].lc) getlst(tr[x].lc);
lst[++tot]=x;
if(tr[x].rc) getlst(tr[x].rc);
}
inline int cmpslope(LL x, LL y, LL z, LL w) {
//x/y>=z/w
assert(y>0&&w>0);
return (__int128)x*w>=(__int128)y*z;
}
void print(int u) {
pushdown(u);
if(tr[u].lc) print(tr[u].lc);
printf("(%lld, %lld) ", tr[u].x, tr[u].y);
if(tr[u].rc) print(tr[u].rc);
}
inline void inspoint(int& nw, int oth) {
//tot=0;
//getlst(nw);
//printf("merge\n");
//for(int i=1; i<=tot; ++i) printf("(%lld, %lld) ", tr[lst[i]].x, tr[lst[i]].y);
//puts("");
//puts("in");
tot=0;
getlst(oth);
//for(int i=1; i<=tot; ++i) printf("(%lld, %lld) ", tr[lst[i]].x, tr[lst[i]].y);
//puts("");
for(int t=1; t<=tot; ++t) {
LL x=tr[lst[t]].x, y=tr[lst[t]].y;
tr[lst[t]].lc=tr[lst[t]].rc=0; tr[lst[t]].ad=0;
tr[lst[t]].sz=1;
int u, v, w, p;
splitval(nw, x, w, v);
splitval(w, x-1, u, p);
if(p!=0&&y>=tr[p].y) {nw=merge(merge(u, p), v); continue;}
int l=0, lp=0, rp=0, r=0;
// printf("u=%d v=%d\n", u, v);
if(u) splitrk(u, tr[u].sz-1, l, lp);
if(v) splitrk(v, 1, rp, r);
//printf("l=%d lp=%d rp=%d r=%d\n", l, lp, rp, r);
if(lp>0&&rp>0) {
if(cmpslope(y-tr[lp].y, x-tr[lp].x, tr[rp].y-tr[lp].y, tr[rp].x-tr[lp].x)) {
nw=merge(merge(l, lp), merge(rp, r));
//printf("ins (%lld, %lld)\n", x, y);
//print(nw);
//puts("");
continue;
}
}
// printf("l=%d lp=%d rp=%d r=%d\n", l, lp, rp, r);
while(l) {
int nl, np;
splitrk(l, tr[l].sz-1, nl, np);
if(cmpslope(tr[lp].y-tr[np].y, tr[lp].x-tr[np].x, y-tr[np].y, x-tr[np].x)) {
l=nl; lp=np;
// printf("del\n");
} else {l=merge(nl, np); break;}
}
while(r) {
int nr, np;
splitrk(r, 1, np, nr);
if(cmpslope(tr[np].y-y, tr[np].x-x, tr[np].y-tr[rp].y, tr[np].x-tr[rp].x)) {
r=nr; rp=np;
} else {r=merge(np, nr); break;}
}
nw=merge(merge(merge(l, lp), lst[t]), merge(rp, r));
//printf("ins (%lld, %lld)\n", x, y);
//print(nw);
//puts("");
}
//printf("result:");
//tot=0;
//getlst(nw);
//for(int i=1; i<=tot; ++i) printf("(%lld, %lld) ", tr[lst[i]].x, tr[lst[i]].y);
//puts("");
//puts("out");
}
void dfs(int x, int F) {
sz[x]=1;
if(la[x]==0) {
f[x]=c[F]*c[x];
rt[x]=add_n(c[x], 0);
return;
}
LL sum=0; int p=0;
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
dfs(y, x);
sum+=f[y]; sz[x]+=sz[y];
if(sz[y]>sz[p]) p=y;
}
rt[x]=rt[p]; tr[rt[x]].ad+=sum-f[p]; tr[rt[x]].y+=sum-f[p];
//if(x==2) {
// print(rt[x]);
//}
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
if(y!=p) tr[rt[y]].ad+=sum-f[y], tr[rt[y]].y+=sum-f[y], inspoint(rt[x], rt[y]);
}
//calc f
//k=-c[F]
int u=rt[x];
pll rb=make_pair(-1, -1);
f[x]=INF;
while(1) {
//getnxt
// if(x==2) printf(" u=%d\n", u);
f[x]=min(f[x], tr[u].y+tr[u].x*c[F]);
pushdown(u);
pll nxt;
if(tr[u].rc) {
int t=tr[u].rc;
while(tr[t].lc) pushdown(t), t=tr[t].lc;
nxt=make_pair(tr[t].x, tr[t].y);
} else nxt=rb;
if(nxt.first==-1) {
if(tr[u].lc==0) break;
rb=make_pair(tr[u].x, tr[u].y);
u=tr[u].lc;
} else {
if(cmpslope(nxt.second-tr[u].y, nxt.first-tr[u].x, -c[F], 1)) {
if(tr[u].lc==0) break;
rb=make_pair(tr[u].x, tr[u].y);
u=tr[u].lc;
} else {
if(tr[u].rc==0) break;
u=tr[u].rc;
}
}
}
}
void prtsbt(int x) {
// printf("x=%d c=%lld\n", x, c[x]);
for(int i=la[x]; i; i=g[i].nxt) {
int y=g[i].y;
printf("%d---%d\n", x, y);
prtsbt(y);
}
}
int main() {
//freopen("3.in", "r", stdin);
//freopen("3.out", "w", stdout);
int n=read();
for(int i=2, x; i<=n; ++i) {
x=read(); add_e(x, i);
}
for(int i=1; i<=n; ++i) c[i]=read();
LL prt=0;
for(int i=la[1]; i; i=g[i].nxt) {
int y=g[i].y;
dfs(y, 1);
prt+=f[y];
}
//printf("fat=%d c=%lld\n", fat, c[fat]);
// for(int i=2; i<=n; ++i) printf("f[%d]=%lld\n", i, f[i]);
printf("%lld", prt);
return 0;
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7864kb
input:
4 1 1 2 2 1 3 2
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5704kb
input:
50 1 2 1 1 2 1 6 3 7 5 11 11 8 10 7 8 9 7 17 2 18 4 23 8 17 21 3 19 2 4 21 18 1 26 21 36 26 24 7 7 29 27 19 29 36 11 29 42 21 15 31 15 40 15 33 2 33 15 6 50 48 33 6 43 36 19 37 28 32 47 50 8 26 50 44 50 31 32 44 22 15 46 11 33 38 22 27 43 29 8 1 21 31 28 26 39 29 39 42
output:
22728
result:
ok 1 number(s): "22728"
Test #3:
score: 0
Accepted
time: 1ms
memory: 7964kb
input:
500 1 1 2 4 3 1 7 2 8 10 8 12 1 7 11 9 14 18 1 17 9 1 16 17 6 14 17 1 26 25 26 29 6 8 7 15 32 9 27 11 34 31 35 6 25 4 35 40 12 2 39 34 21 8 48 8 49 1 39 32 30 46 10 1 45 29 2 17 31 22 30 16 59 10 63 15 71 53 28 50 46 29 59 53 5 3 5 83 48 50 39 18 24 76 6 65 28 72 81 38 54 8 35 88 89 89 18 99 9 99 76...
output:
150134230018
result:
ok 1 number(s): "150134230018"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5920kb
input:
1000 1 1 2 2 4 2 7 3 8 1 9 4 4 4 4 15 3 12 12 6 21 10 20 19 14 23 3 24 26 26 25 31 2 25 28 27 22 38 29 37 16 26 40 5 7 4 25 38 18 41 47 45 14 53 45 18 18 5 10 26 24 59 31 27 58 59 20 47 58 38 29 34 67 68 42 51 44 4 79 7 45 8 73 82 36 51 38 44 77 80 70 21 15 76 40 82 60 61 17 94 46 1 46 25 83 56 57 1...
output:
291482220072
result:
ok 1 number(s): "291482220072"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5860kb
input:
20 1 1 2 3 2 6 1 5 4 7 5 7 9 11 6 7 9 12 4 78702 90933 62714 66603 17557 48708 96257 69094 34701 81307 3224 81752 2616 58113 86806 5963 73405 5059 66996 97390
output:
34002240599
result:
ok 1 number(s): "34002240599"
Test #6:
score: 0
Accepted
time: 34ms
memory: 14812kb
input:
200000 1 2 2 3 1 5 5 8 3 3 1 1 5 13 3 10 15 18 13 5 3 12 18 15 8 8 21 13 4 5 15 8 27 24 20 17 8 26 4 21 36 32 36 42 25 41 25 8 22 37 51 13 26 6 41 26 28 41 13 51 37 35 1 35 28 25 66 14 49 40 24 46 38 20 8 6 15 35 40 2 26 57 65 53 51 17 23 41 14 17 80 54 74 7 32 43 13 49 29 16 17 13 45 51 51 18 20 75...
output:
215275813232282
result:
ok 1 number(s): "215275813232282"
Test #7:
score: 0
Accepted
time: 1ms
memory: 5728kb
input:
8 1 2 2 4 5 2 4 3 6 10 8 3 8 3 10
output:
172
result:
ok 1 number(s): "172"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5728kb
input:
50 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 28 15 6 7 26 12 3 6 1 24 30 29 16 16 18 18 2 8 9 8 17 17 18 25 2 10 45 29 38 6 33 35 44 18 50 12 4 16 20 42 3 19 47 33 31 24 28 42 14 3 28 9 8 21 18 25 37 19 49 2 16 41 9 43 31 6 16 2 11
output:
6044
result:
ok 1 number(s): "6044"
Test #9:
score: 0
Accepted
time: 70ms
memory: 21952kb
input:
200000 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:
7043264795053440
result:
ok 1 number(s): "7043264795053440"
Test #10:
score: 0
Accepted
time: 57ms
memory: 25052kb
input:
200000 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:
16104065120889938
result:
ok 1 number(s): "16104065120889938"
Test #11:
score: 0
Accepted
time: 17ms
memory: 26116kb
input:
200000 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:
10199819800370000
result:
ok 1 number(s): "10199819800370000"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5944kb
input:
19 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 2 18 4 16 6 14 8 12 10 10 12 8 14 6 16 4 18 2 20
output:
700
result:
ok 1 number(s): "700"
Test #13:
score: 0
Accepted
time: 81ms
memory: 20276kb
input:
159999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
341333333600000
result:
ok 1 number(s): "341333333600000"
Test #14:
score: 0
Accepted
time: 95ms
memory: 24192kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
666666667000000
result:
ok 1 number(s): "666666667000000"
Test #15:
score: 0
Accepted
time: 62ms
memory: 24192kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
16666667336033470
result:
ok 1 number(s): "16666667336033470"
Test #16:
score: 0
Accepted
time: 64ms
memory: 24100kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
16666670189471665
result:
ok 1 number(s): "16666670189471665"
Test #17:
score: 0
Accepted
time: 50ms
memory: 24188kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
16666694898519256
result:
ok 1 number(s): "16666694898519256"
Test #18:
score: 0
Accepted
time: 62ms
memory: 14932kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 17 93 95 95 97 88 99 99 6 1...
output:
16364940451965374
result:
ok 1 number(s): "16364940451965374"
Test #19:
score: 0
Accepted
time: 44ms
memory: 14788kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
16379886652909929
result:
ok 1 number(s): "16379886652909929"
Test #20:
score: 0
Accepted
time: 34ms
memory: 14976kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
16376203463318997
result:
ok 1 number(s): "16376203463318997"
Test #21:
score: 0
Accepted
time: 38ms
memory: 15020kb
input:
199999 1 1 2 3 1 4 2 7 3 7 11 11 3 13 15 15 6 17 19 19 10 21 17 17 25 25 13 18 29 29 3 31 29 33 35 26 37 37 36 39 25 41 16 20 2 45 47 47 49 49 11 48 35 13 55 12 57 57 40 16 61 61 33 63 20 65 9 55 69 45 16 71 26 73 10 62 77 77 3 79 80 8 83 83 68 4 87 87 89 89 91 45 93 93 70 90 97 97 47 99 101 79 96 4...
output:
11762207063070191
result:
ok 1 number(s): "11762207063070191"
Test #22:
score: 0
Accepted
time: 37ms
memory: 14048kb
input:
199999 1 1 3 1 5 1 7 1 9 9 5 11 4 4 15 15 10 1 19 19 21 21 23 23 5 25 26 27 29 29 1 12 33 30 35 24 37 37 3 31 41 41 6 43 31 12 47 2 8 48 51 43 53 53 55 18 26 2 59 10 61 61 63 46 65 65 67 67 52 69 65 71 73 25 40 54 18 59 40 79 81 81 22 83 85 85 87 18 89 89 25 91 33 93 35 12 97 97 99 99 60 77 103 16 1...
output:
11786215367156359
result:
ok 1 number(s): "11786215367156359"
Test #23:
score: 0
Accepted
time: 32ms
memory: 14140kb
input:
199999 1 1 3 3 5 3 7 7 6 4 5 1 13 13 15 2 17 17 19 7 11 21 10 5 15 25 14 16 29 29 16 6 33 18 16 32 31 37 39 39 41 41 35 43 5 45 17 47 49 49 47 51 53 45 21 55 57 57 59 19 61 61 1 63 65 65 29 17 27 51 55 11 33 6 75 63 61 77 14 9 5 24 83 24 85 85 87 87 51 72 62 91 93 9 95 11 97 97 97 99 101 101 49 89 8...
output:
11775838097058054
result:
ok 1 number(s): "11775838097058054"
Test #24:
score: 0
Accepted
time: 55ms
memory: 14968kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 18 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 4 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101 ...
output:
16379304442171900
result:
ok 1 number(s): "16379304442171900"
Test #25:
score: 0
Accepted
time: 34ms
memory: 14176kb
input:
199999 1 1 1 3 5 5 7 7 3 1 3 11 13 4 15 14 10 11 19 19 21 21 23 23 23 12 6 14 8 29 31 31 26 9 29 35 37 30 39 39 15 37 25 43 12 45 47 47 6 11 51 9 4 36 55 55 50 57 59 59 61 13 63 8 65 65 67 67 69 69 71 49 16 7 75 75 71 30 79 49 48 81 63 83 85 85 64 48 75 89 3 91 93 23 95 40 97 80 48 99 101 13 103 31 ...
output:
11737863051252300
result:
ok 1 number(s): "11737863051252300"
Test #26:
score: 0
Accepted
time: 17ms
memory: 14704kb
input:
200000 1 2 2 4 3 1 2 1 8 8 11 9 7 4 3 8 16 10 9 9 21 5 7 3 11 21 22 7 26 2 29 11 20 16 4 6 24 5 17 26 34 41 28 21 33 28 13 24 26 10 32 7 17 6 2 7 17 33 37 46 50 29 58 39 16 18 65 35 27 13 5 49 53 6 10 43 63 29 19 63 79 13 4 7 49 39 87 49 27 25 20 72 54 83 65 41 94 74 38 79 9 9 88 31 103 33 48 4 71 1...
output:
216715
result:
ok 1 number(s): "216715"
Test #27:
score: 0
Accepted
time: 28ms
memory: 14796kb
input:
200000 1 2 2 4 2 1 2 8 7 2 2 10 5 7 1 10 12 16 7 10 21 15 7 15 8 13 25 13 6 30 19 14 19 19 8 24 27 31 29 10 22 31 15 19 39 45 17 4 46 25 33 20 51 7 17 35 48 29 3 4 54 44 48 18 13 59 25 48 57 63 33 65 14 4 6 73 26 64 68 49 36 26 71 67 10 4 57 12 22 32 34 12 32 87 19 89 38 50 50 13 82 86 95 19 81 47 1...
output:
373896
result:
ok 1 number(s): "373896"
Test #28:
score: 0
Accepted
time: 19ms
memory: 14640kb
input:
200000 1 2 2 1 3 5 3 6 1 6 7 12 7 12 8 15 14 16 4 10 19 5 11 20 21 20 27 25 19 1 8 24 21 11 1 19 17 30 10 25 13 38 4 7 9 16 14 11 10 21 21 7 28 12 12 20 10 51 3 41 39 24 63 63 5 48 52 40 64 66 48 37 18 23 50 22 52 53 46 62 52 13 54 5 5 56 16 60 36 90 87 48 60 43 64 80 63 62 40 18 88 3 101 41 55 100 ...
output:
816704
result:
ok 1 number(s): "816704"
Test #29:
score: 0
Accepted
time: 85ms
memory: 24444kb
input:
199999 1 1 3 3 5 5 7 7 9 9 11 11 13 13 15 15 17 17 19 19 21 21 23 23 25 25 27 27 29 29 31 31 33 33 35 35 37 37 39 39 41 41 43 43 45 45 47 47 49 49 51 51 53 53 55 55 57 57 59 59 61 61 63 63 65 65 67 67 69 69 71 71 73 73 75 75 77 77 79 79 81 81 83 83 85 85 87 87 89 89 91 91 93 93 95 95 97 97 99 99 101...
output:
666686667100002
result:
ok 1 number(s): "666686667100002"
Test #30:
score: 0
Accepted
time: 62ms
memory: 17644kb
input:
136763 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
155994051912596
result:
ok 1 number(s): "155994051912596"
Test #31:
score: 0
Accepted
time: 98ms
memory: 19284kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166671666750000
result:
ok 1 number(s): "166671666750000"
Test #32:
score: 0
Accepted
time: 87ms
memory: 19492kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166671666950001
result:
ok 1 number(s): "166671666950001"
Test #33:
score: 0
Accepted
time: 90ms
memory: 19988kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166671667549994
result:
ok 1 number(s): "166671667549994"
Test #34:
score: 0
Accepted
time: 88ms
memory: 19428kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166681602663126
result:
ok 1 number(s): "166681602663126"
Test #35:
score: 0
Accepted
time: 86ms
memory: 19288kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166689101385736
result:
ok 1 number(s): "166689101385736"
Test #36:
score: 0
Accepted
time: 85ms
memory: 19536kb
input:
199999 1 2 2 4 4 6 6 8 8 10 10 12 12 14 14 16 16 18 18 20 20 22 22 24 24 26 26 28 28 30 30 32 32 34 34 36 36 38 38 40 40 42 42 44 44 46 46 48 48 50 50 52 52 54 54 56 56 58 58 60 60 62 62 64 64 66 66 68 68 70 70 72 72 74 74 76 76 78 78 80 80 82 82 84 84 86 86 88 88 90 90 92 92 94 94 96 96 98 98 100 1...
output:
166686666599998
result:
ok 1 number(s): "166686666599998"