Submission #675055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
675055	2022-12-27T00:25:51 Z	numberes	Aliens (IOI16_aliens)	C++17	100 / 100	206 ms	18020 KB

aliens

/**
 * @date    2022-12-26 10:42:24
 * @author  numberes
 * 煮不在乎.RAmen!
 */
#include<bits/stdc++.h>
#include "aliens.h"
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define ll long long
using namespace std;
ll g[1000005];
int t[1000005],dq[1000005],dl,dr;
int n,m,k;
int l[1000005],r[1000005],p[1000005];
struct line{
	ll k,b;
}li[1000005];
long double itsect(int a,int b){
	return (long double)(li[b].b-li[a].b)/(li[a].k-li[b].k);
}
void calc(ll c){
	memset(g,0,sizeof(g));memset(t,0,sizeof(t));
	dl=dr=1;dq[1]=1;
	li[1].k=-2*(ll)(l[1]-1);
	li[1].b=g[1]+(ll)(l[1]-1)*(ll)(l[1]-1)+c;
	for(int i=2;i<=n+1;i++){
		while(dl+1<=dr && itsect(dq[dl],dq[dl+1])<r[i-1]) ++dl;
		g[i]=li[dq[dl]].k*r[i-1]+li[dq[dl]].b+(ll)r[i-1]*(ll)r[i-1];
		t[i]=t[dq[dl]]+1;
		li[i].k=-2*(ll)(l[i]-1);
		li[i].b=g[i]+(ll)(l[i]-1)*(ll)(l[i]-1)-(ll)max(0,r[i-1]-l[i]+1)*
		(ll)max(0,r[i-1]-l[i]+1)+c;
		while(dl+1<=dr && itsect(i,dq[dr])<itsect(dq[dr],dq[dr-1])) dr--;
		dq[++dr]=i;
	}
}
ll solve(){
	ll lb=-1,ub=2e12;
	while(lb+1<=ub-1){
		ll mid=(lb+ub)>>1;
		calc(mid);
		if(t[n+1]>k) lb=mid;
		else ub=mid;
	}
	calc(ub);
	return g[n+1]-k*ub;
}
ll take_photos(int _n,int _m,int _k,vector<int> _r,vector<int> _c){
	n=_n;m=_m;k=_k;
	for(int i=0;i<n;i++){
		int le=min(_r[i],_c[i]),ri=max(_r[i],_c[i]);
		p[i]=i;_r[i]=le;_c[i]=ri;
	}
	sort(p,p+n,[&](int a,int b){return (_r[a]!=_r[b]?_r[a]<_r[b]:_c[a]>_c[b]);});
	int tmp=0,mr=-1;
	for(int i=0;i<n;i++)
		if(_c[p[i]]>mr){
			l[++tmp]=_r[p[i]];
			r[tmp]=_c[p[i]];
			mr=_c[p[i]];
		}
	n=tmp;
	return solve();
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12072 KB	Correct answer: answer = 4
2	Correct	52 ms	12068 KB	Correct answer: answer = 4
3	Correct	49 ms	12060 KB	Correct answer: answer = 4
4	Correct	53 ms	12056 KB	Correct answer: answer = 12
5	Correct	52 ms	11988 KB	Correct answer: answer = 52
6	Correct	52 ms	12060 KB	Correct answer: answer = 210
7	Correct	51 ms	12012 KB	Correct answer: answer = 88
8	Correct	55 ms	11988 KB	Correct answer: answer = 7696
9	Correct	49 ms	11988 KB	Correct answer: answer = 1
10	Correct	52 ms	12056 KB	Correct answer: answer = 2374
11	Correct	51 ms	12068 KB	Correct answer: answer = 9502
12	Correct	51 ms	12060 KB	Correct answer: answer = 49
13	Correct	52 ms	12064 KB	Correct answer: answer = 151
14	Correct	54 ms	12076 KB	Correct answer: answer = 7550
15	Correct	58 ms	12068 KB	Correct answer: answer = 7220
16	Correct	59 ms	12056 KB	Correct answer: answer = 7550
17	Correct	55 ms	11988 KB	Correct answer: answer = 10000
18	Correct	49 ms	12060 KB	Correct answer: answer = 10000
19	Correct	51 ms	12060 KB	Correct answer: answer = 624
20	Correct	51 ms	12064 KB	Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	11988 KB	Correct answer: answer = 1
2	Correct	53 ms	12056 KB	Correct answer: answer = 4
3	Correct	51 ms	12056 KB	Correct answer: answer = 1
4	Correct	51 ms	12064 KB	Correct answer: answer = 5
5	Correct	60 ms	12060 KB	Correct answer: answer = 41
6	Correct	53 ms	11988 KB	Correct answer: answer = 71923
7	Correct	55 ms	12080 KB	Correct answer: answer = 77137
8	Correct	52 ms	11988 KB	Correct answer: answer = 764
9	Correct	52 ms	11988 KB	Correct answer: answer = 250000
10	Correct	52 ms	11988 KB	Correct answer: answer = 500
11	Correct	61 ms	12060 KB	Correct answer: answer = 32
12	Correct	54 ms	12084 KB	Correct answer: answer = 130050
13	Correct	55 ms	12084 KB	Correct answer: answer = 5110
14	Correct	57 ms	12012 KB	Correct answer: answer = 2626
15	Correct	57 ms	11988 KB	Correct answer: answer = 796
16	Correct	57 ms	11988 KB	Correct answer: answer = 7580
17	Correct	58 ms	12084 KB	Correct answer: answer = 1904
18	Correct	54 ms	12088 KB	Correct answer: answer = 996004
19	Correct	53 ms	12088 KB	Correct answer: answer = 38817
20	Correct	56 ms	12080 KB	Correct answer: answer = 4096
21	Correct	59 ms	11988 KB	Correct answer: answer = 1
22	Correct	53 ms	11988 KB	Correct answer: answer = 1
23	Correct	61 ms	11988 KB	Correct answer: answer = 2040
24	Correct	49 ms	11988 KB	Correct answer: answer = 2

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12072 KB	Correct answer: answer = 4
2	Correct	52 ms	12068 KB	Correct answer: answer = 4
3	Correct	49 ms	12060 KB	Correct answer: answer = 4
4	Correct	53 ms	12056 KB	Correct answer: answer = 12
5	Correct	52 ms	11988 KB	Correct answer: answer = 52
6	Correct	52 ms	12060 KB	Correct answer: answer = 210
7	Correct	51 ms	12012 KB	Correct answer: answer = 88
8	Correct	55 ms	11988 KB	Correct answer: answer = 7696
9	Correct	49 ms	11988 KB	Correct answer: answer = 1
10	Correct	52 ms	12056 KB	Correct answer: answer = 2374
11	Correct	51 ms	12068 KB	Correct answer: answer = 9502
12	Correct	51 ms	12060 KB	Correct answer: answer = 49
13	Correct	52 ms	12064 KB	Correct answer: answer = 151
14	Correct	54 ms	12076 KB	Correct answer: answer = 7550
15	Correct	58 ms	12068 KB	Correct answer: answer = 7220
16	Correct	59 ms	12056 KB	Correct answer: answer = 7550
17	Correct	55 ms	11988 KB	Correct answer: answer = 10000
18	Correct	49 ms	12060 KB	Correct answer: answer = 10000
19	Correct	51 ms	12060 KB	Correct answer: answer = 624
20	Correct	51 ms	12064 KB	Correct answer: answer = 10000
21	Correct	52 ms	11988 KB	Correct answer: answer = 1
22	Correct	53 ms	12056 KB	Correct answer: answer = 4
23	Correct	51 ms	12056 KB	Correct answer: answer = 1
24	Correct	51 ms	12064 KB	Correct answer: answer = 5
25	Correct	60 ms	12060 KB	Correct answer: answer = 41
26	Correct	53 ms	11988 KB	Correct answer: answer = 71923
27	Correct	55 ms	12080 KB	Correct answer: answer = 77137
28	Correct	52 ms	11988 KB	Correct answer: answer = 764
29	Correct	52 ms	11988 KB	Correct answer: answer = 250000
30	Correct	52 ms	11988 KB	Correct answer: answer = 500
31	Correct	61 ms	12060 KB	Correct answer: answer = 32
32	Correct	54 ms	12084 KB	Correct answer: answer = 130050
33	Correct	55 ms	12084 KB	Correct answer: answer = 5110
34	Correct	57 ms	12012 KB	Correct answer: answer = 2626
35	Correct	57 ms	11988 KB	Correct answer: answer = 796
36	Correct	57 ms	11988 KB	Correct answer: answer = 7580
37	Correct	58 ms	12084 KB	Correct answer: answer = 1904
38	Correct	54 ms	12088 KB	Correct answer: answer = 996004
39	Correct	53 ms	12088 KB	Correct answer: answer = 38817
40	Correct	56 ms	12080 KB	Correct answer: answer = 4096
41	Correct	59 ms	11988 KB	Correct answer: answer = 1
42	Correct	53 ms	11988 KB	Correct answer: answer = 1
43	Correct	61 ms	11988 KB	Correct answer: answer = 2040
44	Correct	49 ms	11988 KB	Correct answer: answer = 2
45	Correct	55 ms	12056 KB	Correct answer: answer = 4
46	Correct	51 ms	11988 KB	Correct answer: answer = 9
47	Correct	50 ms	12056 KB	Correct answer: answer = 9
48	Correct	50 ms	11988 KB	Correct answer: answer = 21
49	Correct	62 ms	12060 KB	Correct answer: answer = 71
50	Correct	51 ms	11988 KB	Correct answer: answer = 77
51	Correct	56 ms	12056 KB	Correct answer: answer = 400
52	Correct	54 ms	12084 KB	Correct answer: answer = 996004
53	Correct	51 ms	11988 KB	Correct answer: answer = 997310
54	Correct	51 ms	12084 KB	Correct answer: answer = 990781
55	Correct	57 ms	12076 KB	Correct answer: answer = 996545
56	Correct	54 ms	12072 KB	Correct answer: answer = 484
57	Correct	52 ms	12084 KB	Correct answer: answer = 484
58	Correct	53 ms	12124 KB	Correct answer: answer = 63501
59	Correct	59 ms	12084 KB	Correct answer: answer = 323501
60	Correct	53 ms	12084 KB	Correct answer: answer = 752500
61	Correct	54 ms	11988 KB	Correct answer: answer = 761480
62	Correct	57 ms	12092 KB	Correct answer: answer = 758932
63	Correct	52 ms	12056 KB	Correct answer: answer = 1000000
64	Correct	53 ms	12080 KB	Correct answer: answer = 750500
65	Correct	58 ms	11988 KB	Correct answer: answer = 1000000
66	Correct	57 ms	12076 KB	Correct answer: answer = 250000
67	Correct	50 ms	12072 KB	Correct answer: answer = 250000
68	Correct	62 ms	12076 KB	Correct answer: answer = 1000000
69	Correct	54 ms	12068 KB	Correct answer: answer = 994009
70	Correct	52 ms	12088 KB	Correct answer: answer = 59315
71	Correct	56 ms	12080 KB	Correct answer: answer = 25454
72	Correct	60 ms	12088 KB	Correct answer: answer = 1504
73	Correct	51 ms	12060 KB	Correct answer: answer = 37486
74	Correct	55 ms	11988 KB	Correct answer: answer = 4284
75	Correct	53 ms	11988 KB	Correct answer: answer = 158008
76	Correct	55 ms	11988 KB	Correct answer: answer = 51860
77	Correct	51 ms	12072 KB	Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12072 KB	Correct answer: answer = 4
2	Correct	52 ms	12068 KB	Correct answer: answer = 4
3	Correct	49 ms	12060 KB	Correct answer: answer = 4
4	Correct	53 ms	12056 KB	Correct answer: answer = 12
5	Correct	52 ms	11988 KB	Correct answer: answer = 52
6	Correct	52 ms	12060 KB	Correct answer: answer = 210
7	Correct	51 ms	12012 KB	Correct answer: answer = 88
8	Correct	55 ms	11988 KB	Correct answer: answer = 7696
9	Correct	49 ms	11988 KB	Correct answer: answer = 1
10	Correct	52 ms	12056 KB	Correct answer: answer = 2374
11	Correct	51 ms	12068 KB	Correct answer: answer = 9502
12	Correct	51 ms	12060 KB	Correct answer: answer = 49
13	Correct	52 ms	12064 KB	Correct answer: answer = 151
14	Correct	54 ms	12076 KB	Correct answer: answer = 7550
15	Correct	58 ms	12068 KB	Correct answer: answer = 7220
16	Correct	59 ms	12056 KB	Correct answer: answer = 7550
17	Correct	55 ms	11988 KB	Correct answer: answer = 10000
18	Correct	49 ms	12060 KB	Correct answer: answer = 10000
19	Correct	51 ms	12060 KB	Correct answer: answer = 624
20	Correct	51 ms	12064 KB	Correct answer: answer = 10000
21	Correct	52 ms	11988 KB	Correct answer: answer = 1
22	Correct	53 ms	12056 KB	Correct answer: answer = 4
23	Correct	51 ms	12056 KB	Correct answer: answer = 1
24	Correct	51 ms	12064 KB	Correct answer: answer = 5
25	Correct	60 ms	12060 KB	Correct answer: answer = 41
26	Correct	53 ms	11988 KB	Correct answer: answer = 71923
27	Correct	55 ms	12080 KB	Correct answer: answer = 77137
28	Correct	52 ms	11988 KB	Correct answer: answer = 764
29	Correct	52 ms	11988 KB	Correct answer: answer = 250000
30	Correct	52 ms	11988 KB	Correct answer: answer = 500
31	Correct	61 ms	12060 KB	Correct answer: answer = 32
32	Correct	54 ms	12084 KB	Correct answer: answer = 130050
33	Correct	55 ms	12084 KB	Correct answer: answer = 5110
34	Correct	57 ms	12012 KB	Correct answer: answer = 2626
35	Correct	57 ms	11988 KB	Correct answer: answer = 796
36	Correct	57 ms	11988 KB	Correct answer: answer = 7580
37	Correct	58 ms	12084 KB	Correct answer: answer = 1904
38	Correct	54 ms	12088 KB	Correct answer: answer = 996004
39	Correct	53 ms	12088 KB	Correct answer: answer = 38817
40	Correct	56 ms	12080 KB	Correct answer: answer = 4096
41	Correct	59 ms	11988 KB	Correct answer: answer = 1
42	Correct	53 ms	11988 KB	Correct answer: answer = 1
43	Correct	61 ms	11988 KB	Correct answer: answer = 2040
44	Correct	49 ms	11988 KB	Correct answer: answer = 2
45	Correct	55 ms	12056 KB	Correct answer: answer = 4
46	Correct	51 ms	11988 KB	Correct answer: answer = 9
47	Correct	50 ms	12056 KB	Correct answer: answer = 9
48	Correct	50 ms	11988 KB	Correct answer: answer = 21
49	Correct	62 ms	12060 KB	Correct answer: answer = 71
50	Correct	51 ms	11988 KB	Correct answer: answer = 77
51	Correct	56 ms	12056 KB	Correct answer: answer = 400
52	Correct	54 ms	12084 KB	Correct answer: answer = 996004
53	Correct	51 ms	11988 KB	Correct answer: answer = 997310
54	Correct	51 ms	12084 KB	Correct answer: answer = 990781
55	Correct	57 ms	12076 KB	Correct answer: answer = 996545
56	Correct	54 ms	12072 KB	Correct answer: answer = 484
57	Correct	52 ms	12084 KB	Correct answer: answer = 484
58	Correct	53 ms	12124 KB	Correct answer: answer = 63501
59	Correct	59 ms	12084 KB	Correct answer: answer = 323501
60	Correct	53 ms	12084 KB	Correct answer: answer = 752500
61	Correct	54 ms	11988 KB	Correct answer: answer = 761480
62	Correct	57 ms	12092 KB	Correct answer: answer = 758932
63	Correct	52 ms	12056 KB	Correct answer: answer = 1000000
64	Correct	53 ms	12080 KB	Correct answer: answer = 750500
65	Correct	58 ms	11988 KB	Correct answer: answer = 1000000
66	Correct	57 ms	12076 KB	Correct answer: answer = 250000
67	Correct	50 ms	12072 KB	Correct answer: answer = 250000
68	Correct	62 ms	12076 KB	Correct answer: answer = 1000000
69	Correct	54 ms	12068 KB	Correct answer: answer = 994009
70	Correct	52 ms	12088 KB	Correct answer: answer = 59315
71	Correct	56 ms	12080 KB	Correct answer: answer = 25454
72	Correct	60 ms	12088 KB	Correct answer: answer = 1504
73	Correct	51 ms	12060 KB	Correct answer: answer = 37486
74	Correct	55 ms	11988 KB	Correct answer: answer = 4284
75	Correct	53 ms	11988 KB	Correct answer: answer = 158008
76	Correct	55 ms	11988 KB	Correct answer: answer = 51860
77	Correct	51 ms	12072 KB	Correct answer: answer = 12985
78	Correct	53 ms	12096 KB	Correct answer: answer = 997864126212
79	Correct	52 ms	12116 KB	Correct answer: answer = 998608411647
80	Correct	51 ms	12188 KB	Correct answer: answer = 995265560477
81	Correct	55 ms	12276 KB	Correct answer: answer = 10125000
82	Correct	56 ms	12396 KB	Correct answer: answer = 2291668
83	Correct	53 ms	12176 KB	Correct answer: answer = 42388
84	Correct	57 ms	12176 KB	Correct answer: answer = 10318
85	Correct	54 ms	12116 KB	Correct answer: answer = 3416
86	Correct	57 ms	12224 KB	Correct answer: answer = 331708193881
87	Correct	61 ms	12284 KB	Correct answer: answer = 2861193756
88	Correct	55 ms	12296 KB	Correct answer: answer = 114646930
89	Correct	56 ms	12408 KB	Correct answer: answer = 9280921
90	Correct	63 ms	12296 KB	Correct answer: answer = 999984053400
91	Correct	58 ms	12284 KB	Correct answer: answer = 750935949134
92	Correct	52 ms	12160 KB	Correct answer: answer = 1000000000000
93	Correct	52 ms	12188 KB	Correct answer: answer = 998762383161
94	Correct	59 ms	12284 KB	Correct answer: answer = 23017412908
95	Correct	56 ms	12192 KB	Correct answer: answer = 728143410622
96	Correct	50 ms	12116 KB	Correct answer: answer = 2
97	Correct	59 ms	12408 KB	Correct answer: answer = 1824916
98	Correct	55 ms	12244 KB	Correct answer: answer = 10680029
99	Correct	56 ms	12288 KB	Correct answer: answer = 18351700
100	Correct	57 ms	12276 KB	Correct answer: answer = 16040026
101	Correct	58 ms	12088 KB	Correct answer: answer = 253968628325
102	Correct	54 ms	12176 KB	Correct answer: answer = 10267
103	Correct	56 ms	12408 KB	Correct answer: answer = 2582408
104	Correct	55 ms	12168 KB	Correct answer: answer = 78024964781
105	Correct	53 ms	12196 KB	Correct answer: answer = 9866346457
106	Correct	55 ms	12200 KB	Correct answer: answer = 3327720949
107	Correct	55 ms	12204 KB	Correct answer: answer = 86064128360
108	Correct	61 ms	12236 KB	Correct answer: answer = 12698259150
109	Correct	59 ms	12272 KB	Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12072 KB	Correct answer: answer = 4
2	Correct	52 ms	12068 KB	Correct answer: answer = 4
3	Correct	49 ms	12060 KB	Correct answer: answer = 4
4	Correct	53 ms	12056 KB	Correct answer: answer = 12
5	Correct	52 ms	11988 KB	Correct answer: answer = 52
6	Correct	52 ms	12060 KB	Correct answer: answer = 210
7	Correct	51 ms	12012 KB	Correct answer: answer = 88
8	Correct	55 ms	11988 KB	Correct answer: answer = 7696
9	Correct	49 ms	11988 KB	Correct answer: answer = 1
10	Correct	52 ms	12056 KB	Correct answer: answer = 2374
11	Correct	51 ms	12068 KB	Correct answer: answer = 9502
12	Correct	51 ms	12060 KB	Correct answer: answer = 49
13	Correct	52 ms	12064 KB	Correct answer: answer = 151
14	Correct	54 ms	12076 KB	Correct answer: answer = 7550
15	Correct	58 ms	12068 KB	Correct answer: answer = 7220
16	Correct	59 ms	12056 KB	Correct answer: answer = 7550
17	Correct	55 ms	11988 KB	Correct answer: answer = 10000
18	Correct	49 ms	12060 KB	Correct answer: answer = 10000
19	Correct	51 ms	12060 KB	Correct answer: answer = 624
20	Correct	51 ms	12064 KB	Correct answer: answer = 10000
21	Correct	52 ms	11988 KB	Correct answer: answer = 1
22	Correct	53 ms	12056 KB	Correct answer: answer = 4
23	Correct	51 ms	12056 KB	Correct answer: answer = 1
24	Correct	51 ms	12064 KB	Correct answer: answer = 5
25	Correct	60 ms	12060 KB	Correct answer: answer = 41
26	Correct	53 ms	11988 KB	Correct answer: answer = 71923
27	Correct	55 ms	12080 KB	Correct answer: answer = 77137
28	Correct	52 ms	11988 KB	Correct answer: answer = 764
29	Correct	52 ms	11988 KB	Correct answer: answer = 250000
30	Correct	52 ms	11988 KB	Correct answer: answer = 500
31	Correct	61 ms	12060 KB	Correct answer: answer = 32
32	Correct	54 ms	12084 KB	Correct answer: answer = 130050
33	Correct	55 ms	12084 KB	Correct answer: answer = 5110
34	Correct	57 ms	12012 KB	Correct answer: answer = 2626
35	Correct	57 ms	11988 KB	Correct answer: answer = 796
36	Correct	57 ms	11988 KB	Correct answer: answer = 7580
37	Correct	58 ms	12084 KB	Correct answer: answer = 1904
38	Correct	54 ms	12088 KB	Correct answer: answer = 996004
39	Correct	53 ms	12088 KB	Correct answer: answer = 38817
40	Correct	56 ms	12080 KB	Correct answer: answer = 4096
41	Correct	59 ms	11988 KB	Correct answer: answer = 1
42	Correct	53 ms	11988 KB	Correct answer: answer = 1
43	Correct	61 ms	11988 KB	Correct answer: answer = 2040
44	Correct	49 ms	11988 KB	Correct answer: answer = 2
45	Correct	55 ms	12056 KB	Correct answer: answer = 4
46	Correct	51 ms	11988 KB	Correct answer: answer = 9
47	Correct	50 ms	12056 KB	Correct answer: answer = 9
48	Correct	50 ms	11988 KB	Correct answer: answer = 21
49	Correct	62 ms	12060 KB	Correct answer: answer = 71
50	Correct	51 ms	11988 KB	Correct answer: answer = 77
51	Correct	56 ms	12056 KB	Correct answer: answer = 400
52	Correct	54 ms	12084 KB	Correct answer: answer = 996004
53	Correct	51 ms	11988 KB	Correct answer: answer = 997310
54	Correct	51 ms	12084 KB	Correct answer: answer = 990781
55	Correct	57 ms	12076 KB	Correct answer: answer = 996545
56	Correct	54 ms	12072 KB	Correct answer: answer = 484
57	Correct	52 ms	12084 KB	Correct answer: answer = 484
58	Correct	53 ms	12124 KB	Correct answer: answer = 63501
59	Correct	59 ms	12084 KB	Correct answer: answer = 323501
60	Correct	53 ms	12084 KB	Correct answer: answer = 752500
61	Correct	54 ms	11988 KB	Correct answer: answer = 761480
62	Correct	57 ms	12092 KB	Correct answer: answer = 758932
63	Correct	52 ms	12056 KB	Correct answer: answer = 1000000
64	Correct	53 ms	12080 KB	Correct answer: answer = 750500
65	Correct	58 ms	11988 KB	Correct answer: answer = 1000000
66	Correct	57 ms	12076 KB	Correct answer: answer = 250000
67	Correct	50 ms	12072 KB	Correct answer: answer = 250000
68	Correct	62 ms	12076 KB	Correct answer: answer = 1000000
69	Correct	54 ms	12068 KB	Correct answer: answer = 994009
70	Correct	52 ms	12088 KB	Correct answer: answer = 59315
71	Correct	56 ms	12080 KB	Correct answer: answer = 25454
72	Correct	60 ms	12088 KB	Correct answer: answer = 1504
73	Correct	51 ms	12060 KB	Correct answer: answer = 37486
74	Correct	55 ms	11988 KB	Correct answer: answer = 4284
75	Correct	53 ms	11988 KB	Correct answer: answer = 158008
76	Correct	55 ms	11988 KB	Correct answer: answer = 51860
77	Correct	51 ms	12072 KB	Correct answer: answer = 12985
78	Correct	53 ms	12096 KB	Correct answer: answer = 997864126212
79	Correct	52 ms	12116 KB	Correct answer: answer = 998608411647
80	Correct	51 ms	12188 KB	Correct answer: answer = 995265560477
81	Correct	55 ms	12276 KB	Correct answer: answer = 10125000
82	Correct	56 ms	12396 KB	Correct answer: answer = 2291668
83	Correct	53 ms	12176 KB	Correct answer: answer = 42388
84	Correct	57 ms	12176 KB	Correct answer: answer = 10318
85	Correct	54 ms	12116 KB	Correct answer: answer = 3416
86	Correct	57 ms	12224 KB	Correct answer: answer = 331708193881
87	Correct	61 ms	12284 KB	Correct answer: answer = 2861193756
88	Correct	55 ms	12296 KB	Correct answer: answer = 114646930
89	Correct	56 ms	12408 KB	Correct answer: answer = 9280921
90	Correct	63 ms	12296 KB	Correct answer: answer = 999984053400
91	Correct	58 ms	12284 KB	Correct answer: answer = 750935949134
92	Correct	52 ms	12160 KB	Correct answer: answer = 1000000000000
93	Correct	52 ms	12188 KB	Correct answer: answer = 998762383161
94	Correct	59 ms	12284 KB	Correct answer: answer = 23017412908
95	Correct	56 ms	12192 KB	Correct answer: answer = 728143410622
96	Correct	50 ms	12116 KB	Correct answer: answer = 2
97	Correct	59 ms	12408 KB	Correct answer: answer = 1824916
98	Correct	55 ms	12244 KB	Correct answer: answer = 10680029
99	Correct	56 ms	12288 KB	Correct answer: answer = 18351700
100	Correct	57 ms	12276 KB	Correct answer: answer = 16040026
101	Correct	58 ms	12088 KB	Correct answer: answer = 253968628325
102	Correct	54 ms	12176 KB	Correct answer: answer = 10267
103	Correct	56 ms	12408 KB	Correct answer: answer = 2582408
104	Correct	55 ms	12168 KB	Correct answer: answer = 78024964781
105	Correct	53 ms	12196 KB	Correct answer: answer = 9866346457
106	Correct	55 ms	12200 KB	Correct answer: answer = 3327720949
107	Correct	55 ms	12204 KB	Correct answer: answer = 86064128360
108	Correct	61 ms	12236 KB	Correct answer: answer = 12698259150
109	Correct	59 ms	12272 KB	Correct answer: answer = 1185259288
110	Correct	69 ms	13616 KB	Correct answer: answer = 999889968863
111	Correct	68 ms	13724 KB	Correct answer: answer = 999861384931
112	Correct	73 ms	13720 KB	Correct answer: answer = 999811809929
113	Correct	65 ms	13612 KB	Correct answer: answer = 999869756441
114	Correct	98 ms	14848 KB	Correct answer: answer = 1700000000
115	Correct	102 ms	15044 KB	Correct answer: answer = 131666670
116	Correct	65 ms	12980 KB	Correct answer: answer = 89478486
117	Correct	84 ms	12956 KB	Correct answer: answer = 4971040
118	Correct	69 ms	12992 KB	Correct answer: answer = 2711494
119	Correct	99 ms	14932 KB	Correct answer: answer = 25252530
120	Correct	95 ms	14916 KB	Correct answer: answer = 62500000
121	Correct	124 ms	14840 KB	Correct answer: answer = 333175097780
122	Correct	127 ms	14844 KB	Correct answer: answer = 33121180179
123	Correct	130 ms	14856 KB	Correct answer: answer = 9802314015
124	Correct	101 ms	14976 KB	Correct answer: answer = 32567551
125	Correct	94 ms	14924 KB	Correct answer: answer = 997525000000
126	Correct	119 ms	14672 KB	Correct answer: answer = 752723538884
127	Correct	62 ms	13564 KB	Correct answer: answer = 1000000000000
128	Correct	63 ms	13644 KB	Correct answer: answer = 999978000121
129	Correct	69 ms	13644 KB	Correct answer: answer = 745986144735
130	Correct	60 ms	13368 KB	Correct answer: answer = 2
131	Correct	97 ms	14948 KB	Correct answer: answer = 277966670
132	Correct	94 ms	14880 KB	Correct answer: answer = 2500900082
133	Correct	69 ms	13780 KB	Correct answer: answer = 301248349636
134	Correct	89 ms	13584 KB	Correct answer: answer = 14118891
135	Correct	65 ms	13696 KB	Correct answer: answer = 14384977265
136	Correct	64 ms	13652 KB	Correct answer: answer = 3681368330
137	Correct	64 ms	13644 KB	Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	12072 KB	Correct answer: answer = 4
2	Correct	52 ms	12068 KB	Correct answer: answer = 4
3	Correct	49 ms	12060 KB	Correct answer: answer = 4
4	Correct	53 ms	12056 KB	Correct answer: answer = 12
5	Correct	52 ms	11988 KB	Correct answer: answer = 52
6	Correct	52 ms	12060 KB	Correct answer: answer = 210
7	Correct	51 ms	12012 KB	Correct answer: answer = 88
8	Correct	55 ms	11988 KB	Correct answer: answer = 7696
9	Correct	49 ms	11988 KB	Correct answer: answer = 1
10	Correct	52 ms	12056 KB	Correct answer: answer = 2374
11	Correct	51 ms	12068 KB	Correct answer: answer = 9502
12	Correct	51 ms	12060 KB	Correct answer: answer = 49
13	Correct	52 ms	12064 KB	Correct answer: answer = 151
14	Correct	54 ms	12076 KB	Correct answer: answer = 7550
15	Correct	58 ms	12068 KB	Correct answer: answer = 7220
16	Correct	59 ms	12056 KB	Correct answer: answer = 7550
17	Correct	55 ms	11988 KB	Correct answer: answer = 10000
18	Correct	49 ms	12060 KB	Correct answer: answer = 10000
19	Correct	51 ms	12060 KB	Correct answer: answer = 624
20	Correct	51 ms	12064 KB	Correct answer: answer = 10000
21	Correct	52 ms	11988 KB	Correct answer: answer = 1
22	Correct	53 ms	12056 KB	Correct answer: answer = 4
23	Correct	51 ms	12056 KB	Correct answer: answer = 1
24	Correct	51 ms	12064 KB	Correct answer: answer = 5
25	Correct	60 ms	12060 KB	Correct answer: answer = 41
26	Correct	53 ms	11988 KB	Correct answer: answer = 71923
27	Correct	55 ms	12080 KB	Correct answer: answer = 77137
28	Correct	52 ms	11988 KB	Correct answer: answer = 764
29	Correct	52 ms	11988 KB	Correct answer: answer = 250000
30	Correct	52 ms	11988 KB	Correct answer: answer = 500
31	Correct	61 ms	12060 KB	Correct answer: answer = 32
32	Correct	54 ms	12084 KB	Correct answer: answer = 130050
33	Correct	55 ms	12084 KB	Correct answer: answer = 5110
34	Correct	57 ms	12012 KB	Correct answer: answer = 2626
35	Correct	57 ms	11988 KB	Correct answer: answer = 796
36	Correct	57 ms	11988 KB	Correct answer: answer = 7580
37	Correct	58 ms	12084 KB	Correct answer: answer = 1904
38	Correct	54 ms	12088 KB	Correct answer: answer = 996004
39	Correct	53 ms	12088 KB	Correct answer: answer = 38817
40	Correct	56 ms	12080 KB	Correct answer: answer = 4096
41	Correct	59 ms	11988 KB	Correct answer: answer = 1
42	Correct	53 ms	11988 KB	Correct answer: answer = 1
43	Correct	61 ms	11988 KB	Correct answer: answer = 2040
44	Correct	49 ms	11988 KB	Correct answer: answer = 2
45	Correct	55 ms	12056 KB	Correct answer: answer = 4
46	Correct	51 ms	11988 KB	Correct answer: answer = 9
47	Correct	50 ms	12056 KB	Correct answer: answer = 9
48	Correct	50 ms	11988 KB	Correct answer: answer = 21
49	Correct	62 ms	12060 KB	Correct answer: answer = 71
50	Correct	51 ms	11988 KB	Correct answer: answer = 77
51	Correct	56 ms	12056 KB	Correct answer: answer = 400
52	Correct	54 ms	12084 KB	Correct answer: answer = 996004
53	Correct	51 ms	11988 KB	Correct answer: answer = 997310
54	Correct	51 ms	12084 KB	Correct answer: answer = 990781
55	Correct	57 ms	12076 KB	Correct answer: answer = 996545
56	Correct	54 ms	12072 KB	Correct answer: answer = 484
57	Correct	52 ms	12084 KB	Correct answer: answer = 484
58	Correct	53 ms	12124 KB	Correct answer: answer = 63501
59	Correct	59 ms	12084 KB	Correct answer: answer = 323501
60	Correct	53 ms	12084 KB	Correct answer: answer = 752500
61	Correct	54 ms	11988 KB	Correct answer: answer = 761480
62	Correct	57 ms	12092 KB	Correct answer: answer = 758932
63	Correct	52 ms	12056 KB	Correct answer: answer = 1000000
64	Correct	53 ms	12080 KB	Correct answer: answer = 750500
65	Correct	58 ms	11988 KB	Correct answer: answer = 1000000
66	Correct	57 ms	12076 KB	Correct answer: answer = 250000
67	Correct	50 ms	12072 KB	Correct answer: answer = 250000
68	Correct	62 ms	12076 KB	Correct answer: answer = 1000000
69	Correct	54 ms	12068 KB	Correct answer: answer = 994009
70	Correct	52 ms	12088 KB	Correct answer: answer = 59315
71	Correct	56 ms	12080 KB	Correct answer: answer = 25454
72	Correct	60 ms	12088 KB	Correct answer: answer = 1504
73	Correct	51 ms	12060 KB	Correct answer: answer = 37486
74	Correct	55 ms	11988 KB	Correct answer: answer = 4284
75	Correct	53 ms	11988 KB	Correct answer: answer = 158008
76	Correct	55 ms	11988 KB	Correct answer: answer = 51860
77	Correct	51 ms	12072 KB	Correct answer: answer = 12985
78	Correct	53 ms	12096 KB	Correct answer: answer = 997864126212
79	Correct	52 ms	12116 KB	Correct answer: answer = 998608411647
80	Correct	51 ms	12188 KB	Correct answer: answer = 995265560477
81	Correct	55 ms	12276 KB	Correct answer: answer = 10125000
82	Correct	56 ms	12396 KB	Correct answer: answer = 2291668
83	Correct	53 ms	12176 KB	Correct answer: answer = 42388
84	Correct	57 ms	12176 KB	Correct answer: answer = 10318
85	Correct	54 ms	12116 KB	Correct answer: answer = 3416
86	Correct	57 ms	12224 KB	Correct answer: answer = 331708193881
87	Correct	61 ms	12284 KB	Correct answer: answer = 2861193756
88	Correct	55 ms	12296 KB	Correct answer: answer = 114646930
89	Correct	56 ms	12408 KB	Correct answer: answer = 9280921
90	Correct	63 ms	12296 KB	Correct answer: answer = 999984053400
91	Correct	58 ms	12284 KB	Correct answer: answer = 750935949134
92	Correct	52 ms	12160 KB	Correct answer: answer = 1000000000000
93	Correct	52 ms	12188 KB	Correct answer: answer = 998762383161
94	Correct	59 ms	12284 KB	Correct answer: answer = 23017412908
95	Correct	56 ms	12192 KB	Correct answer: answer = 728143410622
96	Correct	50 ms	12116 KB	Correct answer: answer = 2
97	Correct	59 ms	12408 KB	Correct answer: answer = 1824916
98	Correct	55 ms	12244 KB	Correct answer: answer = 10680029
99	Correct	56 ms	12288 KB	Correct answer: answer = 18351700
100	Correct	57 ms	12276 KB	Correct answer: answer = 16040026
101	Correct	58 ms	12088 KB	Correct answer: answer = 253968628325
102	Correct	54 ms	12176 KB	Correct answer: answer = 10267
103	Correct	56 ms	12408 KB	Correct answer: answer = 2582408
104	Correct	55 ms	12168 KB	Correct answer: answer = 78024964781
105	Correct	53 ms	12196 KB	Correct answer: answer = 9866346457
106	Correct	55 ms	12200 KB	Correct answer: answer = 3327720949
107	Correct	55 ms	12204 KB	Correct answer: answer = 86064128360
108	Correct	61 ms	12236 KB	Correct answer: answer = 12698259150
109	Correct	59 ms	12272 KB	Correct answer: answer = 1185259288
110	Correct	69 ms	13616 KB	Correct answer: answer = 999889968863
111	Correct	68 ms	13724 KB	Correct answer: answer = 999861384931
112	Correct	73 ms	13720 KB	Correct answer: answer = 999811809929
113	Correct	65 ms	13612 KB	Correct answer: answer = 999869756441
114	Correct	98 ms	14848 KB	Correct answer: answer = 1700000000
115	Correct	102 ms	15044 KB	Correct answer: answer = 131666670
116	Correct	65 ms	12980 KB	Correct answer: answer = 89478486
117	Correct	84 ms	12956 KB	Correct answer: answer = 4971040
118	Correct	69 ms	12992 KB	Correct answer: answer = 2711494
119	Correct	99 ms	14932 KB	Correct answer: answer = 25252530
120	Correct	95 ms	14916 KB	Correct answer: answer = 62500000
121	Correct	124 ms	14840 KB	Correct answer: answer = 333175097780
122	Correct	127 ms	14844 KB	Correct answer: answer = 33121180179
123	Correct	130 ms	14856 KB	Correct answer: answer = 9802314015
124	Correct	101 ms	14976 KB	Correct answer: answer = 32567551
125	Correct	94 ms	14924 KB	Correct answer: answer = 997525000000
126	Correct	119 ms	14672 KB	Correct answer: answer = 752723538884
127	Correct	62 ms	13564 KB	Correct answer: answer = 1000000000000
128	Correct	63 ms	13644 KB	Correct answer: answer = 999978000121
129	Correct	69 ms	13644 KB	Correct answer: answer = 745986144735
130	Correct	60 ms	13368 KB	Correct answer: answer = 2
131	Correct	97 ms	14948 KB	Correct answer: answer = 277966670
132	Correct	94 ms	14880 KB	Correct answer: answer = 2500900082
133	Correct	69 ms	13780 KB	Correct answer: answer = 301248349636
134	Correct	89 ms	13584 KB	Correct answer: answer = 14118891
135	Correct	65 ms	13696 KB	Correct answer: answer = 14384977265
136	Correct	64 ms	13652 KB	Correct answer: answer = 3681368330
137	Correct	64 ms	13644 KB	Correct answer: answer = 2720316816
138	Correct	78 ms	14576 KB	Correct answer: answer = 999976000144
139	Correct	83 ms	15284 KB	Correct answer: answer = 999856102410
140	Correct	80 ms	15308 KB	Correct answer: answer = 999958401531
141	Correct	78 ms	15288 KB	Correct answer: answer = 999769649944
142	Correct	74 ms	15380 KB	Correct answer: answer = 999874525918
143	Correct	141 ms	17720 KB	Correct answer: answer = 6050000000
144	Correct	150 ms	17824 KB	Correct answer: answer = 1112500000
145	Correct	121 ms	15792 KB	Correct answer: answer = 4294967296
146	Correct	109 ms	15800 KB	Correct answer: answer = 87652406
147	Correct	110 ms	15904 KB	Correct answer: answer = 6297664
148	Correct	104 ms	15788 KB	Correct answer: answer = 196612
149	Correct	140 ms	17868 KB	Correct answer: answer = 15015100
150	Correct	139 ms	17848 KB	Correct answer: answer = 25000000
151	Correct	193 ms	17616 KB	Correct answer: answer = 333230209550
152	Correct	206 ms	17612 KB	Correct answer: answer = 917123769
153	Correct	189 ms	17872 KB	Correct answer: answer = 95162
154	Correct	141 ms	17844 KB	Correct answer: answer = 382616191
155	Correct	139 ms	17972 KB	Correct answer: answer = 990033333400
156	Correct	138 ms	18020 KB	Correct answer: answer = 990000100000
157	Correct	182 ms	17476 KB	Correct answer: answer = 749998188180
158	Correct	69 ms	15272 KB	Correct answer: answer = 1000000000000
159	Correct	75 ms	15284 KB	Correct answer: answer = 999988000036
160	Correct	80 ms	15308 KB	Correct answer: answer = 744929274393
161	Correct	69 ms	14424 KB	Correct answer: answer = 2
162	Correct	135 ms	17832 KB	Correct answer: answer = 1300024
163	Correct	137 ms	17728 KB	Correct answer: answer = 5000700010
164	Correct	91 ms	15564 KB	Correct answer: answer = 354997100800
165	Correct	123 ms	14892 KB	Correct answer: answer = 257000
166	Correct	113 ms	15080 KB	Correct answer: answer = 3765323
167	Correct	114 ms	15012 KB	Correct answer: answer = 1525903
168	Correct	84 ms	15280 KB	Correct answer: answer = 67618137730
169	Correct	85 ms	15308 KB	Correct answer: answer = 12656680171
170	Correct	84 ms	15344 KB	Correct answer: answer = 579831736
171	Correct	112 ms	16060 KB	Correct answer: answer = 23605611
172	Correct	83 ms	15484 KB	Correct answer: answer = 7052481200
173	Correct	85 ms	15652 KB	Correct answer: answer = 1314039500
174	Correct	94 ms	15984 KB	Correct answer: answer = 302484000
175	Correct	119 ms	16844 KB	Correct answer: answer = 52348480

Submission #675055

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 12.0 / 12.0

Subtask #3 9.0 / 9.0

Subtask #4 16.0 / 16.0

Subtask #5 19.0 / 19.0

Subtask #6 40.0 / 40.0

Subtask #1
4.0 / 4.0

Subtask #2
12.0 / 12.0

Subtask #3
9.0 / 9.0

Subtask #4
16.0 / 16.0

Subtask #5
19.0 / 19.0

Subtask #6
40.0 / 40.0