Submission #43618

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
43618	2018-03-18T09:07:23 Z	Namnamseo	Aliens (IOI16_aliens)	C++14	100 / 100	154 ms	66836 KB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef pair<int,int> pp;
typedef long long ll;

pp po[100010];
ll x[100010];
ll y[100010];
int pn;

ll dp[100010];

int top;
ll grad[100010];
ll yint[100010];
int lid[100010];
void add_line(ll g, ll y, int id){
	while(top>=2){
		if((yint[top-2]-yint[top-1])*(grad[top-1]-g)>
		(yint[top-1]-y)*(grad[top-2]-grad[top-1])) break;
		--top;
	}
	grad[top] = g;
	yint[top] = y;
	lid[top] = id;
	++top;
}
int bx;
ll f(int p, ll x){ return grad[p]*x + yint[p]; }
inline ll sqr(ll x){ return x*x; }
int lst[100010];
int F(ll cost){
	top = 0; bx = 0;
	add_line(-2*x[0], sqr(x[0]), -1);
	for(int i=0; i<pn; ++i){
		while(bx+1 < top && f(bx, y[i]+1) > f(bx+1, y[i]+1)) ++bx;
		dp[i]=f(bx, y[i]+1)+sqr(y[i]+1)+cost;
		lst[i]=lid[bx];
		if(i+1 < pn){
			add_line(-2*x[i+1], dp[i]+sqr(x[i+1])-sqr(max(0ll, y[i]-x[i+1]+1)), i);
			bx = min(bx, top-1);
		}
	}
	int cnt = 0;
	for(int i=pn-1; i!=-1; i=lst[i]) ++cnt;
	return cnt;
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	for(int i=0; i<n; ++i){
		int x=r[i], y=c[i];
		if(x>y) swap(x, y);
		po[i]={x, y};
	}
	sort(po, po+n);
	for(int i=0; i<n; ++i){
		int cx=po[i].first, cy=po[i].second;
		if(!pn){
			x[pn]=cx; y[pn]=cy; ++pn;
			continue;
		}
		if(x[pn-1] == cx) y[pn-1] = cy;
		else if(y[pn-1] < cy) x[pn]=cx, y[pn]=cy, ++pn;
	}
	ll cl = -1, cr = m*1LL*m;
	while(cl+1 < cr){
		ll mid = (cl+cr)/2;
		(F(mid) <= k ? cr : cl) = mid;
	}
	F(cr);
	return dp[pn-1]-cr*k;
}

Subtask #1
4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Correct answer: answer = 4
2	Correct	2 ms	376 KB	Correct answer: answer = 4
3	Correct	2 ms	552 KB	Correct answer: answer = 4
4	Correct	2 ms	552 KB	Correct answer: answer = 12
5	Correct	2 ms	620 KB	Correct answer: answer = 52
6	Correct	2 ms	620 KB	Correct answer: answer = 210
7	Correct	2 ms	620 KB	Correct answer: answer = 88
8	Correct	2 ms	624 KB	Correct answer: answer = 7696
9	Correct	2 ms	644 KB	Correct answer: answer = 1
10	Correct	2 ms	648 KB	Correct answer: answer = 2374
11	Correct	2 ms	740 KB	Correct answer: answer = 9502
12	Correct	2 ms	780 KB	Correct answer: answer = 49
13	Correct	1 ms	780 KB	Correct answer: answer = 151
14	Correct	2 ms	780 KB	Correct answer: answer = 7550
15	Correct	2 ms	856 KB	Correct answer: answer = 7220
16	Correct	2 ms	856 KB	Correct answer: answer = 7550
17	Correct	1 ms	856 KB	Correct answer: answer = 10000
18	Correct	1 ms	856 KB	Correct answer: answer = 10000
19	Correct	2 ms	856 KB	Correct answer: answer = 624
20	Correct	2 ms	856 KB	Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	856 KB	Correct answer: answer = 1
2	Correct	1 ms	856 KB	Correct answer: answer = 4
3	Correct	2 ms	856 KB	Correct answer: answer = 1
4	Correct	1 ms	856 KB	Correct answer: answer = 5
5	Correct	1 ms	856 KB	Correct answer: answer = 41
6	Correct	1 ms	856 KB	Correct answer: answer = 71923
7	Correct	1 ms	856 KB	Correct answer: answer = 77137
8	Correct	2 ms	856 KB	Correct answer: answer = 764
9	Correct	2 ms	856 KB	Correct answer: answer = 250000
10	Correct	2 ms	856 KB	Correct answer: answer = 500
11	Correct	1 ms	856 KB	Correct answer: answer = 32
12	Correct	2 ms	856 KB	Correct answer: answer = 130050
13	Correct	2 ms	856 KB	Correct answer: answer = 5110
14	Correct	2 ms	856 KB	Correct answer: answer = 2626
15	Correct	2 ms	856 KB	Correct answer: answer = 796
16	Correct	2 ms	856 KB	Correct answer: answer = 7580
17	Correct	2 ms	856 KB	Correct answer: answer = 1904
18	Correct	2 ms	856 KB	Correct answer: answer = 996004
19	Correct	2 ms	856 KB	Correct answer: answer = 38817
20	Correct	2 ms	856 KB	Correct answer: answer = 4096
21	Correct	2 ms	856 KB	Correct answer: answer = 1
22	Correct	1 ms	856 KB	Correct answer: answer = 1
23	Correct	2 ms	856 KB	Correct answer: answer = 2040
24	Correct	1 ms	856 KB	Correct answer: answer = 2

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Correct answer: answer = 4
2	Correct	2 ms	376 KB	Correct answer: answer = 4
3	Correct	2 ms	552 KB	Correct answer: answer = 4
4	Correct	2 ms	552 KB	Correct answer: answer = 12
5	Correct	2 ms	620 KB	Correct answer: answer = 52
6	Correct	2 ms	620 KB	Correct answer: answer = 210
7	Correct	2 ms	620 KB	Correct answer: answer = 88
8	Correct	2 ms	624 KB	Correct answer: answer = 7696
9	Correct	2 ms	644 KB	Correct answer: answer = 1
10	Correct	2 ms	648 KB	Correct answer: answer = 2374
11	Correct	2 ms	740 KB	Correct answer: answer = 9502
12	Correct	2 ms	780 KB	Correct answer: answer = 49
13	Correct	1 ms	780 KB	Correct answer: answer = 151
14	Correct	2 ms	780 KB	Correct answer: answer = 7550
15	Correct	2 ms	856 KB	Correct answer: answer = 7220
16	Correct	2 ms	856 KB	Correct answer: answer = 7550
17	Correct	1 ms	856 KB	Correct answer: answer = 10000
18	Correct	1 ms	856 KB	Correct answer: answer = 10000
19	Correct	2 ms	856 KB	Correct answer: answer = 624
20	Correct	2 ms	856 KB	Correct answer: answer = 10000
21	Correct	1 ms	856 KB	Correct answer: answer = 1
22	Correct	1 ms	856 KB	Correct answer: answer = 4
23	Correct	2 ms	856 KB	Correct answer: answer = 1
24	Correct	1 ms	856 KB	Correct answer: answer = 5
25	Correct	1 ms	856 KB	Correct answer: answer = 41
26	Correct	1 ms	856 KB	Correct answer: answer = 71923
27	Correct	1 ms	856 KB	Correct answer: answer = 77137
28	Correct	2 ms	856 KB	Correct answer: answer = 764
29	Correct	2 ms	856 KB	Correct answer: answer = 250000
30	Correct	2 ms	856 KB	Correct answer: answer = 500
31	Correct	1 ms	856 KB	Correct answer: answer = 32
32	Correct	2 ms	856 KB	Correct answer: answer = 130050
33	Correct	2 ms	856 KB	Correct answer: answer = 5110
34	Correct	2 ms	856 KB	Correct answer: answer = 2626
35	Correct	2 ms	856 KB	Correct answer: answer = 796
36	Correct	2 ms	856 KB	Correct answer: answer = 7580
37	Correct	2 ms	856 KB	Correct answer: answer = 1904
38	Correct	2 ms	856 KB	Correct answer: answer = 996004
39	Correct	2 ms	856 KB	Correct answer: answer = 38817
40	Correct	2 ms	856 KB	Correct answer: answer = 4096
41	Correct	2 ms	856 KB	Correct answer: answer = 1
42	Correct	1 ms	856 KB	Correct answer: answer = 1
43	Correct	2 ms	856 KB	Correct answer: answer = 2040
44	Correct	1 ms	856 KB	Correct answer: answer = 2
45	Correct	2 ms	856 KB	Correct answer: answer = 4
46	Correct	2 ms	856 KB	Correct answer: answer = 9
47	Correct	1 ms	856 KB	Correct answer: answer = 9
48	Correct	1 ms	856 KB	Correct answer: answer = 21
49	Correct	2 ms	856 KB	Correct answer: answer = 71
50	Correct	1 ms	856 KB	Correct answer: answer = 77
51	Correct	1 ms	856 KB	Correct answer: answer = 400
52	Correct	2 ms	856 KB	Correct answer: answer = 996004
53	Correct	2 ms	856 KB	Correct answer: answer = 997310
54	Correct	2 ms	904 KB	Correct answer: answer = 990781
55	Correct	2 ms	904 KB	Correct answer: answer = 996545
56	Correct	2 ms	904 KB	Correct answer: answer = 484
57	Correct	2 ms	904 KB	Correct answer: answer = 484
58	Correct	2 ms	904 KB	Correct answer: answer = 63501
59	Correct	2 ms	904 KB	Correct answer: answer = 323501
60	Correct	2 ms	904 KB	Correct answer: answer = 752500
61	Correct	2 ms	904 KB	Correct answer: answer = 761480
62	Correct	2 ms	928 KB	Correct answer: answer = 758932
63	Correct	2 ms	928 KB	Correct answer: answer = 1000000
64	Correct	2 ms	928 KB	Correct answer: answer = 750500
65	Correct	2 ms	928 KB	Correct answer: answer = 1000000
66	Correct	2 ms	928 KB	Correct answer: answer = 250000
67	Correct	2 ms	928 KB	Correct answer: answer = 250000
68	Correct	2 ms	928 KB	Correct answer: answer = 1000000
69	Correct	2 ms	928 KB	Correct answer: answer = 994009
70	Correct	2 ms	928 KB	Correct answer: answer = 59315
71	Correct	2 ms	928 KB	Correct answer: answer = 25454
72	Correct	2 ms	928 KB	Correct answer: answer = 1504
73	Correct	2 ms	928 KB	Correct answer: answer = 37486
74	Correct	2 ms	928 KB	Correct answer: answer = 4284
75	Correct	2 ms	928 KB	Correct answer: answer = 158008
76	Correct	2 ms	928 KB	Correct answer: answer = 51860
77	Correct	2 ms	928 KB	Correct answer: answer = 12985
78	Correct	3 ms	988 KB	Correct answer: answer = 997864126212
79	Correct	3 ms	1104 KB	Correct answer: answer = 998608411647
80	Correct	3 ms	1172 KB	Correct answer: answer = 995265560477
81	Correct	6 ms	1360 KB	Correct answer: answer = 10125000
82	Correct	4 ms	1400 KB	Correct answer: answer = 2291668
83	Correct	3 ms	1400 KB	Correct answer: answer = 42388
84	Correct	3 ms	1400 KB	Correct answer: answer = 10318
85	Correct	3 ms	1400 KB	Correct answer: answer = 3416
86	Correct	7 ms	1500 KB	Correct answer: answer = 331708193881
87	Correct	6 ms	1604 KB	Correct answer: answer = 2861193756
88	Correct	7 ms	1660 KB	Correct answer: answer = 114646930
89	Correct	4 ms	1716 KB	Correct answer: answer = 9280921
90	Correct	6 ms	1756 KB	Correct answer: answer = 999984053400
91	Correct	7 ms	1804 KB	Correct answer: answer = 750935949134
92	Correct	2 ms	1804 KB	Correct answer: answer = 1000000000000
93	Correct	3 ms	1804 KB	Correct answer: answer = 998762383161
94	Correct	6 ms	1964 KB	Correct answer: answer = 23017412908
95	Correct	3 ms	1964 KB	Correct answer: answer = 728143410622
96	Correct	2 ms	2020 KB	Correct answer: answer = 2
97	Correct	6 ms	2092 KB	Correct answer: answer = 1824916
98	Correct	6 ms	2188 KB	Correct answer: answer = 10680029
99	Correct	6 ms	2188 KB	Correct answer: answer = 18351700
100	Correct	5 ms	2228 KB	Correct answer: answer = 16040026
101	Correct	3 ms	2228 KB	Correct answer: answer = 253968628325
102	Correct	4 ms	2228 KB	Correct answer: answer = 10267
103	Correct	5 ms	2416 KB	Correct answer: answer = 2582408
104	Correct	3 ms	2416 KB	Correct answer: answer = 78024964781
105	Correct	4 ms	2416 KB	Correct answer: answer = 9866346457
106	Correct	3 ms	2416 KB	Correct answer: answer = 3327720949
107	Correct	3 ms	2428 KB	Correct answer: answer = 86064128360
108	Correct	4 ms	2484 KB	Correct answer: answer = 12698259150
109	Correct	5 ms	2708 KB	Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Correct answer: answer = 4
2	Correct	2 ms	376 KB	Correct answer: answer = 4
3	Correct	2 ms	552 KB	Correct answer: answer = 4
4	Correct	2 ms	552 KB	Correct answer: answer = 12
5	Correct	2 ms	620 KB	Correct answer: answer = 52
6	Correct	2 ms	620 KB	Correct answer: answer = 210
7	Correct	2 ms	620 KB	Correct answer: answer = 88
8	Correct	2 ms	624 KB	Correct answer: answer = 7696
9	Correct	2 ms	644 KB	Correct answer: answer = 1
10	Correct	2 ms	648 KB	Correct answer: answer = 2374
11	Correct	2 ms	740 KB	Correct answer: answer = 9502
12	Correct	2 ms	780 KB	Correct answer: answer = 49
13	Correct	1 ms	780 KB	Correct answer: answer = 151
14	Correct	2 ms	780 KB	Correct answer: answer = 7550
15	Correct	2 ms	856 KB	Correct answer: answer = 7220
16	Correct	2 ms	856 KB	Correct answer: answer = 7550
17	Correct	1 ms	856 KB	Correct answer: answer = 10000
18	Correct	1 ms	856 KB	Correct answer: answer = 10000
19	Correct	2 ms	856 KB	Correct answer: answer = 624
20	Correct	2 ms	856 KB	Correct answer: answer = 10000
21	Correct	1 ms	856 KB	Correct answer: answer = 1
22	Correct	1 ms	856 KB	Correct answer: answer = 4
23	Correct	2 ms	856 KB	Correct answer: answer = 1
24	Correct	1 ms	856 KB	Correct answer: answer = 5
25	Correct	1 ms	856 KB	Correct answer: answer = 41
26	Correct	1 ms	856 KB	Correct answer: answer = 71923
27	Correct	1 ms	856 KB	Correct answer: answer = 77137
28	Correct	2 ms	856 KB	Correct answer: answer = 764
29	Correct	2 ms	856 KB	Correct answer: answer = 250000
30	Correct	2 ms	856 KB	Correct answer: answer = 500
31	Correct	1 ms	856 KB	Correct answer: answer = 32
32	Correct	2 ms	856 KB	Correct answer: answer = 130050
33	Correct	2 ms	856 KB	Correct answer: answer = 5110
34	Correct	2 ms	856 KB	Correct answer: answer = 2626
35	Correct	2 ms	856 KB	Correct answer: answer = 796
36	Correct	2 ms	856 KB	Correct answer: answer = 7580
37	Correct	2 ms	856 KB	Correct answer: answer = 1904
38	Correct	2 ms	856 KB	Correct answer: answer = 996004
39	Correct	2 ms	856 KB	Correct answer: answer = 38817
40	Correct	2 ms	856 KB	Correct answer: answer = 4096
41	Correct	2 ms	856 KB	Correct answer: answer = 1
42	Correct	1 ms	856 KB	Correct answer: answer = 1
43	Correct	2 ms	856 KB	Correct answer: answer = 2040
44	Correct	1 ms	856 KB	Correct answer: answer = 2
45	Correct	2 ms	856 KB	Correct answer: answer = 4
46	Correct	2 ms	856 KB	Correct answer: answer = 9
47	Correct	1 ms	856 KB	Correct answer: answer = 9
48	Correct	1 ms	856 KB	Correct answer: answer = 21
49	Correct	2 ms	856 KB	Correct answer: answer = 71
50	Correct	1 ms	856 KB	Correct answer: answer = 77
51	Correct	1 ms	856 KB	Correct answer: answer = 400
52	Correct	2 ms	856 KB	Correct answer: answer = 996004
53	Correct	2 ms	856 KB	Correct answer: answer = 997310
54	Correct	2 ms	904 KB	Correct answer: answer = 990781
55	Correct	2 ms	904 KB	Correct answer: answer = 996545
56	Correct	2 ms	904 KB	Correct answer: answer = 484
57	Correct	2 ms	904 KB	Correct answer: answer = 484
58	Correct	2 ms	904 KB	Correct answer: answer = 63501
59	Correct	2 ms	904 KB	Correct answer: answer = 323501
60	Correct	2 ms	904 KB	Correct answer: answer = 752500
61	Correct	2 ms	904 KB	Correct answer: answer = 761480
62	Correct	2 ms	928 KB	Correct answer: answer = 758932
63	Correct	2 ms	928 KB	Correct answer: answer = 1000000
64	Correct	2 ms	928 KB	Correct answer: answer = 750500
65	Correct	2 ms	928 KB	Correct answer: answer = 1000000
66	Correct	2 ms	928 KB	Correct answer: answer = 250000
67	Correct	2 ms	928 KB	Correct answer: answer = 250000
68	Correct	2 ms	928 KB	Correct answer: answer = 1000000
69	Correct	2 ms	928 KB	Correct answer: answer = 994009
70	Correct	2 ms	928 KB	Correct answer: answer = 59315
71	Correct	2 ms	928 KB	Correct answer: answer = 25454
72	Correct	2 ms	928 KB	Correct answer: answer = 1504
73	Correct	2 ms	928 KB	Correct answer: answer = 37486
74	Correct	2 ms	928 KB	Correct answer: answer = 4284
75	Correct	2 ms	928 KB	Correct answer: answer = 158008
76	Correct	2 ms	928 KB	Correct answer: answer = 51860
77	Correct	2 ms	928 KB	Correct answer: answer = 12985
78	Correct	3 ms	988 KB	Correct answer: answer = 997864126212
79	Correct	3 ms	1104 KB	Correct answer: answer = 998608411647
80	Correct	3 ms	1172 KB	Correct answer: answer = 995265560477
81	Correct	6 ms	1360 KB	Correct answer: answer = 10125000
82	Correct	4 ms	1400 KB	Correct answer: answer = 2291668
83	Correct	3 ms	1400 KB	Correct answer: answer = 42388
84	Correct	3 ms	1400 KB	Correct answer: answer = 10318
85	Correct	3 ms	1400 KB	Correct answer: answer = 3416
86	Correct	7 ms	1500 KB	Correct answer: answer = 331708193881
87	Correct	6 ms	1604 KB	Correct answer: answer = 2861193756
88	Correct	7 ms	1660 KB	Correct answer: answer = 114646930
89	Correct	4 ms	1716 KB	Correct answer: answer = 9280921
90	Correct	6 ms	1756 KB	Correct answer: answer = 999984053400
91	Correct	7 ms	1804 KB	Correct answer: answer = 750935949134
92	Correct	2 ms	1804 KB	Correct answer: answer = 1000000000000
93	Correct	3 ms	1804 KB	Correct answer: answer = 998762383161
94	Correct	6 ms	1964 KB	Correct answer: answer = 23017412908
95	Correct	3 ms	1964 KB	Correct answer: answer = 728143410622
96	Correct	2 ms	2020 KB	Correct answer: answer = 2
97	Correct	6 ms	2092 KB	Correct answer: answer = 1824916
98	Correct	6 ms	2188 KB	Correct answer: answer = 10680029
99	Correct	6 ms	2188 KB	Correct answer: answer = 18351700
100	Correct	5 ms	2228 KB	Correct answer: answer = 16040026
101	Correct	3 ms	2228 KB	Correct answer: answer = 253968628325
102	Correct	4 ms	2228 KB	Correct answer: answer = 10267
103	Correct	5 ms	2416 KB	Correct answer: answer = 2582408
104	Correct	3 ms	2416 KB	Correct answer: answer = 78024964781
105	Correct	4 ms	2416 KB	Correct answer: answer = 9866346457
106	Correct	3 ms	2416 KB	Correct answer: answer = 3327720949
107	Correct	3 ms	2428 KB	Correct answer: answer = 86064128360
108	Correct	4 ms	2484 KB	Correct answer: answer = 12698259150
109	Correct	5 ms	2708 KB	Correct answer: answer = 1185259288
110	Correct	20 ms	4260 KB	Correct answer: answer = 999889968863
111	Correct	20 ms	4936 KB	Correct answer: answer = 999861384931
112	Correct	21 ms	5616 KB	Correct answer: answer = 999811809929
113	Correct	21 ms	6292 KB	Correct answer: answer = 999869756441
114	Correct	38 ms	8632 KB	Correct answer: answer = 1700000000
115	Correct	40 ms	9584 KB	Correct answer: answer = 131666670
116	Correct	11 ms	9584 KB	Correct answer: answer = 89478486
117	Correct	13 ms	9584 KB	Correct answer: answer = 4971040
118	Correct	12 ms	9584 KB	Correct answer: answer = 2711494
119	Correct	45 ms	10808 KB	Correct answer: answer = 25252530
120	Correct	37 ms	11512 KB	Correct answer: answer = 62500000
121	Correct	61 ms	11512 KB	Correct answer: answer = 333175097780
122	Correct	60 ms	11872 KB	Correct answer: answer = 33121180179
123	Correct	66 ms	12676 KB	Correct answer: answer = 9802314015
124	Correct	41 ms	13984 KB	Correct answer: answer = 32567551
125	Correct	50 ms	14688 KB	Correct answer: answer = 997525000000
126	Correct	64 ms	14688 KB	Correct answer: answer = 752723538884
127	Correct	14 ms	14688 KB	Correct answer: answer = 1000000000000
128	Correct	20 ms	14688 KB	Correct answer: answer = 999978000121
129	Correct	20 ms	15000 KB	Correct answer: answer = 745986144735
130	Correct	12 ms	15176 KB	Correct answer: answer = 2
131	Correct	52 ms	17932 KB	Correct answer: answer = 277966670
132	Correct	44 ms	18244 KB	Correct answer: answer = 2500900082
133	Correct	29 ms	18244 KB	Correct answer: answer = 301248349636
134	Correct	28 ms	18244 KB	Correct answer: answer = 14118891
135	Correct	20 ms	18244 KB	Correct answer: answer = 14384977265
136	Correct	21 ms	18644 KB	Correct answer: answer = 3681368330
137	Correct	21 ms	19336 KB	Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Correct answer: answer = 4
2	Correct	2 ms	376 KB	Correct answer: answer = 4
3	Correct	2 ms	552 KB	Correct answer: answer = 4
4	Correct	2 ms	552 KB	Correct answer: answer = 12
5	Correct	2 ms	620 KB	Correct answer: answer = 52
6	Correct	2 ms	620 KB	Correct answer: answer = 210
7	Correct	2 ms	620 KB	Correct answer: answer = 88
8	Correct	2 ms	624 KB	Correct answer: answer = 7696
9	Correct	2 ms	644 KB	Correct answer: answer = 1
10	Correct	2 ms	648 KB	Correct answer: answer = 2374
11	Correct	2 ms	740 KB	Correct answer: answer = 9502
12	Correct	2 ms	780 KB	Correct answer: answer = 49
13	Correct	1 ms	780 KB	Correct answer: answer = 151
14	Correct	2 ms	780 KB	Correct answer: answer = 7550
15	Correct	2 ms	856 KB	Correct answer: answer = 7220
16	Correct	2 ms	856 KB	Correct answer: answer = 7550
17	Correct	1 ms	856 KB	Correct answer: answer = 10000
18	Correct	1 ms	856 KB	Correct answer: answer = 10000
19	Correct	2 ms	856 KB	Correct answer: answer = 624
20	Correct	2 ms	856 KB	Correct answer: answer = 10000
21	Correct	1 ms	856 KB	Correct answer: answer = 1
22	Correct	1 ms	856 KB	Correct answer: answer = 4
23	Correct	2 ms	856 KB	Correct answer: answer = 1
24	Correct	1 ms	856 KB	Correct answer: answer = 5
25	Correct	1 ms	856 KB	Correct answer: answer = 41
26	Correct	1 ms	856 KB	Correct answer: answer = 71923
27	Correct	1 ms	856 KB	Correct answer: answer = 77137
28	Correct	2 ms	856 KB	Correct answer: answer = 764
29	Correct	2 ms	856 KB	Correct answer: answer = 250000
30	Correct	2 ms	856 KB	Correct answer: answer = 500
31	Correct	1 ms	856 KB	Correct answer: answer = 32
32	Correct	2 ms	856 KB	Correct answer: answer = 130050
33	Correct	2 ms	856 KB	Correct answer: answer = 5110
34	Correct	2 ms	856 KB	Correct answer: answer = 2626
35	Correct	2 ms	856 KB	Correct answer: answer = 796
36	Correct	2 ms	856 KB	Correct answer: answer = 7580
37	Correct	2 ms	856 KB	Correct answer: answer = 1904
38	Correct	2 ms	856 KB	Correct answer: answer = 996004
39	Correct	2 ms	856 KB	Correct answer: answer = 38817
40	Correct	2 ms	856 KB	Correct answer: answer = 4096
41	Correct	2 ms	856 KB	Correct answer: answer = 1
42	Correct	1 ms	856 KB	Correct answer: answer = 1
43	Correct	2 ms	856 KB	Correct answer: answer = 2040
44	Correct	1 ms	856 KB	Correct answer: answer = 2
45	Correct	2 ms	856 KB	Correct answer: answer = 4
46	Correct	2 ms	856 KB	Correct answer: answer = 9
47	Correct	1 ms	856 KB	Correct answer: answer = 9
48	Correct	1 ms	856 KB	Correct answer: answer = 21
49	Correct	2 ms	856 KB	Correct answer: answer = 71
50	Correct	1 ms	856 KB	Correct answer: answer = 77
51	Correct	1 ms	856 KB	Correct answer: answer = 400
52	Correct	2 ms	856 KB	Correct answer: answer = 996004
53	Correct	2 ms	856 KB	Correct answer: answer = 997310
54	Correct	2 ms	904 KB	Correct answer: answer = 990781
55	Correct	2 ms	904 KB	Correct answer: answer = 996545
56	Correct	2 ms	904 KB	Correct answer: answer = 484
57	Correct	2 ms	904 KB	Correct answer: answer = 484
58	Correct	2 ms	904 KB	Correct answer: answer = 63501
59	Correct	2 ms	904 KB	Correct answer: answer = 323501
60	Correct	2 ms	904 KB	Correct answer: answer = 752500
61	Correct	2 ms	904 KB	Correct answer: answer = 761480
62	Correct	2 ms	928 KB	Correct answer: answer = 758932
63	Correct	2 ms	928 KB	Correct answer: answer = 1000000
64	Correct	2 ms	928 KB	Correct answer: answer = 750500
65	Correct	2 ms	928 KB	Correct answer: answer = 1000000
66	Correct	2 ms	928 KB	Correct answer: answer = 250000
67	Correct	2 ms	928 KB	Correct answer: answer = 250000
68	Correct	2 ms	928 KB	Correct answer: answer = 1000000
69	Correct	2 ms	928 KB	Correct answer: answer = 994009
70	Correct	2 ms	928 KB	Correct answer: answer = 59315
71	Correct	2 ms	928 KB	Correct answer: answer = 25454
72	Correct	2 ms	928 KB	Correct answer: answer = 1504
73	Correct	2 ms	928 KB	Correct answer: answer = 37486
74	Correct	2 ms	928 KB	Correct answer: answer = 4284
75	Correct	2 ms	928 KB	Correct answer: answer = 158008
76	Correct	2 ms	928 KB	Correct answer: answer = 51860
77	Correct	2 ms	928 KB	Correct answer: answer = 12985
78	Correct	3 ms	988 KB	Correct answer: answer = 997864126212
79	Correct	3 ms	1104 KB	Correct answer: answer = 998608411647
80	Correct	3 ms	1172 KB	Correct answer: answer = 995265560477
81	Correct	6 ms	1360 KB	Correct answer: answer = 10125000
82	Correct	4 ms	1400 KB	Correct answer: answer = 2291668
83	Correct	3 ms	1400 KB	Correct answer: answer = 42388
84	Correct	3 ms	1400 KB	Correct answer: answer = 10318
85	Correct	3 ms	1400 KB	Correct answer: answer = 3416
86	Correct	7 ms	1500 KB	Correct answer: answer = 331708193881
87	Correct	6 ms	1604 KB	Correct answer: answer = 2861193756
88	Correct	7 ms	1660 KB	Correct answer: answer = 114646930
89	Correct	4 ms	1716 KB	Correct answer: answer = 9280921
90	Correct	6 ms	1756 KB	Correct answer: answer = 999984053400
91	Correct	7 ms	1804 KB	Correct answer: answer = 750935949134
92	Correct	2 ms	1804 KB	Correct answer: answer = 1000000000000
93	Correct	3 ms	1804 KB	Correct answer: answer = 998762383161
94	Correct	6 ms	1964 KB	Correct answer: answer = 23017412908
95	Correct	3 ms	1964 KB	Correct answer: answer = 728143410622
96	Correct	2 ms	2020 KB	Correct answer: answer = 2
97	Correct	6 ms	2092 KB	Correct answer: answer = 1824916
98	Correct	6 ms	2188 KB	Correct answer: answer = 10680029
99	Correct	6 ms	2188 KB	Correct answer: answer = 18351700
100	Correct	5 ms	2228 KB	Correct answer: answer = 16040026
101	Correct	3 ms	2228 KB	Correct answer: answer = 253968628325
102	Correct	4 ms	2228 KB	Correct answer: answer = 10267
103	Correct	5 ms	2416 KB	Correct answer: answer = 2582408
104	Correct	3 ms	2416 KB	Correct answer: answer = 78024964781
105	Correct	4 ms	2416 KB	Correct answer: answer = 9866346457
106	Correct	3 ms	2416 KB	Correct answer: answer = 3327720949
107	Correct	3 ms	2428 KB	Correct answer: answer = 86064128360
108	Correct	4 ms	2484 KB	Correct answer: answer = 12698259150
109	Correct	5 ms	2708 KB	Correct answer: answer = 1185259288
110	Correct	20 ms	4260 KB	Correct answer: answer = 999889968863
111	Correct	20 ms	4936 KB	Correct answer: answer = 999861384931
112	Correct	21 ms	5616 KB	Correct answer: answer = 999811809929
113	Correct	21 ms	6292 KB	Correct answer: answer = 999869756441
114	Correct	38 ms	8632 KB	Correct answer: answer = 1700000000
115	Correct	40 ms	9584 KB	Correct answer: answer = 131666670
116	Correct	11 ms	9584 KB	Correct answer: answer = 89478486
117	Correct	13 ms	9584 KB	Correct answer: answer = 4971040
118	Correct	12 ms	9584 KB	Correct answer: answer = 2711494
119	Correct	45 ms	10808 KB	Correct answer: answer = 25252530
120	Correct	37 ms	11512 KB	Correct answer: answer = 62500000
121	Correct	61 ms	11512 KB	Correct answer: answer = 333175097780
122	Correct	60 ms	11872 KB	Correct answer: answer = 33121180179
123	Correct	66 ms	12676 KB	Correct answer: answer = 9802314015
124	Correct	41 ms	13984 KB	Correct answer: answer = 32567551
125	Correct	50 ms	14688 KB	Correct answer: answer = 997525000000
126	Correct	64 ms	14688 KB	Correct answer: answer = 752723538884
127	Correct	14 ms	14688 KB	Correct answer: answer = 1000000000000
128	Correct	20 ms	14688 KB	Correct answer: answer = 999978000121
129	Correct	20 ms	15000 KB	Correct answer: answer = 745986144735
130	Correct	12 ms	15176 KB	Correct answer: answer = 2
131	Correct	52 ms	17932 KB	Correct answer: answer = 277966670
132	Correct	44 ms	18244 KB	Correct answer: answer = 2500900082
133	Correct	29 ms	18244 KB	Correct answer: answer = 301248349636
134	Correct	28 ms	18244 KB	Correct answer: answer = 14118891
135	Correct	20 ms	18244 KB	Correct answer: answer = 14384977265
136	Correct	21 ms	18644 KB	Correct answer: answer = 3681368330
137	Correct	21 ms	19336 KB	Correct answer: answer = 2720316816
138	Correct	40 ms	21860 KB	Correct answer: answer = 999976000144
139	Correct	44 ms	23196 KB	Correct answer: answer = 999856102410
140	Correct	44 ms	24564 KB	Correct answer: answer = 999958401531
141	Correct	54 ms	25904 KB	Correct answer: answer = 999769649944
142	Correct	41 ms	27352 KB	Correct answer: answer = 999874525918
143	Correct	79 ms	32076 KB	Correct answer: answer = 6050000000
144	Correct	89 ms	33632 KB	Correct answer: answer = 1112500000
145	Correct	40 ms	33632 KB	Correct answer: answer = 4294967296
146	Correct	55 ms	33632 KB	Correct answer: answer = 87652406
147	Correct	52 ms	34144 KB	Correct answer: answer = 6297664
148	Correct	52 ms	34884 KB	Correct answer: answer = 196612
149	Correct	82 ms	38500 KB	Correct answer: answer = 15015100
150	Correct	79 ms	39652 KB	Correct answer: answer = 25000000
151	Correct	120 ms	39652 KB	Correct answer: answer = 333230209550
152	Correct	126 ms	40360 KB	Correct answer: answer = 917123769
153	Correct	154 ms	43520 KB	Correct answer: answer = 95162
154	Correct	83 ms	44648 KB	Correct answer: answer = 382616191
155	Correct	92 ms	46004 KB	Correct answer: answer = 990033333400
156	Correct	91 ms	47428 KB	Correct answer: answer = 990000100000
157	Correct	112 ms	47516 KB	Correct answer: answer = 749998188180
158	Correct	28 ms	47516 KB	Correct answer: answer = 1000000000000
159	Correct	42 ms	47516 KB	Correct answer: answer = 999988000036
160	Correct	42 ms	48052 KB	Correct answer: answer = 744929274393
161	Correct	21 ms	48420 KB	Correct answer: answer = 2
162	Correct	100 ms	54312 KB	Correct answer: answer = 1300024
163	Correct	95 ms	54568 KB	Correct answer: answer = 5000700010
164	Correct	51 ms	54568 KB	Correct answer: answer = 354997100800
165	Correct	67 ms	54568 KB	Correct answer: answer = 257000
166	Correct	58 ms	54568 KB	Correct answer: answer = 3765323
167	Correct	56 ms	55032 KB	Correct answer: answer = 1525903
168	Correct	41 ms	55288 KB	Correct answer: answer = 67618137730
169	Correct	49 ms	56692 KB	Correct answer: answer = 12656680171
170	Correct	44 ms	58028 KB	Correct answer: answer = 579831736
171	Correct	74 ms	60364 KB	Correct answer: answer = 23605611
172	Correct	43 ms	60856 KB	Correct answer: answer = 7052481200
173	Correct	48 ms	62588 KB	Correct answer: answer = 1314039500
174	Correct	49 ms	64336 KB	Correct answer: answer = 302484000
175	Correct	73 ms	66836 KB	Correct answer: answer = 52348480

Submission #43618

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