oj.uz

Submission #140599

# Submission time Handle Problem Language Result Execution time Memory
140599 2019-08-03T16:34:02 Z mosesmayer Aliens (IOI16_aliens) C++17
100 / 100
 150 ms 10348 KB 
#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
 
struct Line{
	LL m, c, i;
	Line(LL m = 0, LL c = 0, int i = 0): m(m), c(c), i(i) {}
	LL get(LL x){return m * x + c;}
};
struct ConvexHull{
	int sz, B, fr;
	Line *hull;
	ConvexHull(int n): sz(0), B(0), fr(0){
		hull = new Line[++n];
	}
	bool is_bad(int curr, int prev, int next){
		Line c = hull[curr], p = hull[prev], n = hull[next];
		return (c.c - n.c) * (c.m - p.m) <= (p.c - c.c) * (n.m - c.m);
	}
	void add_line(LL m, LL c, int idx){
		hull[sz++] = Line(m, c, idx);
		while (sz - fr > 2 && is_bad(sz-2, sz-3, sz-1)){
			hull[sz-2] = hull[sz-1]; sz--;
		}
	}
 
	pair<LL, int> query(LL x){
		while (sz - fr > 1 && hull[fr].get(x) >= hull[fr+1].get(x)) fr++;
		return make_pair(hull[fr].get(x), hull[fr].i);
	}
};
 
const LL LINF = 1e18;
const int MX = 1e5;
int n, m, k;
vector<pii> ori;
LL L[MX + 5], R[MX + 5], nx[MX + 5];
LL dp[MX + 5];
LL dp2[2][MX + 5];
int cnt[MX + 5];
int par[MX + 5];
ConvexHull ch(MX + 5);
 
bool cmp(pii a, pii b){
	return a.fi != b.fi ? a.fi < b.fi : a.se > b.se;
}
 
/*
   dp[k][n] = min(dp[k-1][n], min{j<=n} (dp[k-1][j-1] + (L[j]^2-2L[j]) + max(0,R[j-1]-L[j]+1)^2 - 2L[j]•R[n]) + R[n]^2 + 2R[n] + 1;
										(             c1             )   (      c2            ) (  m  ) ( x )   (   extra        )
										(R[n] - L[j] + 1) ^ 2 = (R[n] + 1) ^ 2 - 2L[j](R[n] + 1) + L[j] ^ 2
*/
 
LL check(LL C){
	ch.sz = 0; ch.fr = 0;
	cnt[0] = 0;
	for (int j = 1; j <= n; j++){
		ch.add_line(-2LL * L[j], dp[j-1] + L[j] * L[j] - nx[j] * nx[j], j-1);
		pair<LL, int> res = ch.query(R[j] + 1);
		dp[j] = res.first + (R[j] + 1) * (R[j] + 1) + C;
		par[j] = res.second;
		cnt[j] = cnt[par[j]] + 1;
//		cout << "J/" << j << " : " << dp[j] << ' ' << cnt[j] << ' ' << par[j] << '\n';
	}
//	cout << "Checking C : " << C << " with result " << dp[n] << ' ' << cnt[n] << '\n';
	return cnt[n];
}
long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) {
	n = N, m = M, k = K;
	for (int i = 0; i < n; i++){
		ori.emplace_back(r[i], c[i]);
		if (ori.back().fi > ori.back().se) swap(ori.back().fi, ori.back().se);
	}
	sort(ori.begin(), ori.end());
	int idx = 0;
	for (int i = 0; i < n; i++){
		if (idx && L[idx] <= ori[i].fi && R[idx] >= ori[i].se) continue;
		while (idx && ori[i].fi <= L[idx] && ori[i].se >= R[idx]) idx--;
		idx++; tie(L[idx], R[idx]) = ori[i];
	}
	n = idx;
	k = min(k, idx);
//	for (int i = 1; i <= n; i++) printf("(%d, %d)%c", L[i], R[i], " \n"[i==n]);
 
	L[0] = R[0] = -LINF;
	for (int i = 1; i <= n; i++)
		nx[i] = max(0LL, R[i-1] - L[i] + 1);
//	for (int i = 1; i <= n; i++) printf("%lld%c", nx[i], " \n"[i==n]);
//	for (int j = 1; j <= n; j++) dp2[0][j] = LINF;
//	for (int i = 1; i <= k; i++){
//		ch.sz = ch.fr = 0;
//		for (int j = 1; j <= n; j++){
//			ch.add_line(-2LL * L[j], dp2[i&1^1][j-1] + L[j] * L[j] - nx[j] * nx[j], cnt[j - 1]);
//			pair<LL, int> res = ch.query(R[j] + 1);
//			dp2[i&1][j] = res.first + (R[j] + 1) * (R[j] + 1);
//			cnt[j] = res.second + 1;
//	//		cout << "J/" << j << " : " << dp[j] << ' ' << cnt[j] << '\n';
//		}
//	}
//	return dp2[k&1][n];
	LL lo = -1e12, hi = 1e12, md, ans = -1e12;
	//increase cost then k decreases
//	cout << "LOOK FOR K : " << k << '\n';
	while (lo <= hi){
		md = (lo + hi) >> 1;
		if (check(md) <= k){
			ans = md; hi = md - 1;
		} else lo = md + 1;
	}
	int kk = check(ans);
//	cout << ans << ' ' << kk << '\n';
	return dp[n] - ans * kk - 1LL * (k - kk) * (ans - 1);
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct answer: answer = 4
2 Correct 4 ms 2680 KB Correct answer: answer = 4
3 Correct 4 ms 2680 KB Correct answer: answer = 4
4 Correct 4 ms 2680 KB Correct answer: answer = 12
5 Correct 4 ms 2680 KB Correct answer: answer = 52
6 Correct 4 ms 2808 KB Correct answer: answer = 210
7 Correct 4 ms 2680 KB Correct answer: answer = 88
8 Correct 4 ms 2680 KB Correct answer: answer = 7696
9 Correct 4 ms 2680 KB Correct answer: answer = 1
10 Correct 4 ms 2680 KB Correct answer: answer = 2374
11 Correct 4 ms 2728 KB Correct answer: answer = 9502
12 Correct 4 ms 2680 KB Correct answer: answer = 49
13 Correct 4 ms 2680 KB Correct answer: answer = 151
14 Correct 4 ms 2680 KB Correct answer: answer = 7550
15 Correct 4 ms 2680 KB Correct answer: answer = 7220
16 Correct 4 ms 2680 KB Correct answer: answer = 7550
17 Correct 4 ms 2680 KB Correct answer: answer = 10000
18 Correct 4 ms 2680 KB Correct answer: answer = 10000
19 Correct 4 ms 2680 KB Correct answer: answer = 624
20 Correct 4 ms 2680 KB Correct answer: answer = 10000
21 Correct 4 ms 2680 KB Correct answer: answer = 1
22 Correct 4 ms 2680 KB Correct answer: answer = 4
23 Correct 5 ms 2680 KB Correct answer: answer = 1
24 Correct 4 ms 2680 KB Correct answer: answer = 5
25 Correct 4 ms 2680 KB Correct answer: answer = 41
26 Correct 4 ms 2680 KB Correct answer: answer = 71923
27 Correct 4 ms 2680 KB Correct answer: answer = 77137
28 Correct 5 ms 2808 KB Correct answer: answer = 764
29 Correct 5 ms 2808 KB Correct answer: answer = 250000
30 Correct 4 ms 2808 KB Correct answer: answer = 500
31 Correct 4 ms 2680 KB Correct answer: answer = 32
32 Correct 4 ms 2808 KB Correct answer: answer = 130050
33 Correct 4 ms 2680 KB Correct answer: answer = 5110
34 Correct 4 ms 2680 KB Correct answer: answer = 2626
35 Correct 4 ms 2680 KB Correct answer: answer = 796
36 Correct 4 ms 2808 KB Correct answer: answer = 7580
37 Correct 4 ms 2808 KB Correct answer: answer = 1904
38 Correct 5 ms 2808 KB Correct answer: answer = 996004
39 Correct 4 ms 2808 KB Correct answer: answer = 38817
40 Correct 4 ms 2808 KB Correct answer: answer = 4096
41 Correct 4 ms 2680 KB Correct answer: answer = 1
42 Correct 5 ms 2680 KB Correct answer: answer = 1
43 Correct 5 ms 2808 KB Correct answer: answer = 2040
44 Correct 4 ms 2680 KB Correct answer: answer = 2
45 Correct 4 ms 2684 KB Correct answer: answer = 4
46 Correct 4 ms 2680 KB Correct answer: answer = 9
47 Correct 4 ms 2680 KB Correct answer: answer = 9
48 Correct 4 ms 2680 KB Correct answer: answer = 21
49 Correct 4 ms 2680 KB Correct answer: answer = 71
50 Correct 4 ms 2680 KB Correct answer: answer = 77
51 Correct 4 ms 2680 KB Correct answer: answer = 400
52 Correct 4 ms 2680 KB Correct answer: answer = 996004
53 Correct 4 ms 2680 KB Correct answer: answer = 997310
54 Correct 4 ms 2680 KB Correct answer: answer = 990781
55 Correct 4 ms 2680 KB Correct answer: answer = 996545
56 Correct 4 ms 2808 KB Correct answer: answer = 484
57 Correct 4 ms 2680 KB Correct answer: answer = 484
58 Correct 4 ms 2808 KB Correct answer: answer = 63501
59 Correct 5 ms 2808 KB Correct answer: answer = 323501
60 Correct 5 ms 2808 KB Correct answer: answer = 752500
61 Correct 5 ms 2680 KB Correct answer: answer = 761480
62 Correct 4 ms 2808 KB Correct answer: answer = 758932
63 Correct 4 ms 2680 KB Correct answer: answer = 1000000
64 Correct 4 ms 2808 KB Correct answer: answer = 750500
65 Correct 4 ms 2808 KB Correct answer: answer = 1000000
66 Correct 4 ms 2808 KB Correct answer: answer = 250000
67 Correct 4 ms 2764 KB Correct answer: answer = 250000
68 Correct 3 ms 2680 KB Correct answer: answer = 1000000
69 Correct 4 ms 2680 KB Correct answer: answer = 994009
70 Correct 8 ms 2808 KB Correct answer: answer = 59315
71 Correct 5 ms 2808 KB Correct answer: answer = 25454
72 Correct 5 ms 2680 KB Correct answer: answer = 1504
73 Correct 5 ms 2680 KB Correct answer: answer = 37486
74 Correct 4 ms 2680 KB Correct answer: answer = 4284
75 Correct 4 ms 2680 KB Correct answer: answer = 158008
76 Correct 4 ms 2680 KB Correct answer: answer = 51860
77 Correct 4 ms 2680 KB Correct answer: answer = 12985
78 Correct 6 ms 2812 KB Correct answer: answer = 997864126212
79 Correct 6 ms 2936 KB Correct answer: answer = 998608411647
80 Correct 6 ms 2812 KB Correct answer: answer = 995265560477
81 Correct 8 ms 3064 KB Correct answer: answer = 10125000
82 Correct 0 ms 3064 KB Correct answer: answer = 2291668
83 Correct 7 ms 2808 KB Correct answer: answer = 42388
84 Correct 7 ms 2808 KB Correct answer: answer = 10318
85 Correct 7 ms 2936 KB Correct answer: answer = 3416
86 Correct 15 ms 3064 KB Correct answer: answer = 331708193881
87 Correct 9 ms 3064 KB Correct answer: answer = 2861193756
88 Correct 10 ms 3064 KB Correct answer: answer = 114646930
89 Correct 8 ms 2936 KB Correct answer: answer = 9280921
90 Correct 8 ms 3064 KB Correct answer: answer = 999984053400
91 Correct 9 ms 3064 KB Correct answer: answer = 750935949134
92 Correct 5 ms 2936 KB Correct answer: answer = 1000000000000
93 Correct 5 ms 2808 KB Correct answer: answer = 998762383161
94 Correct 10 ms 3064 KB Correct answer: answer = 23017412908
95 Correct 8 ms 2936 KB Correct answer: answer = 728143410622
96 Correct 5 ms 2896 KB Correct answer: answer = 2
97 Correct 8 ms 3064 KB Correct answer: answer = 1824916
98 Correct 8 ms 3064 KB Correct answer: answer = 10680029
99 Correct 8 ms 3064 KB Correct answer: answer = 18351700
100 Correct 8 ms 3064 KB Correct answer: answer = 16040026
101 Correct 6 ms 2936 KB Correct answer: answer = 253968628325
102 Correct 4 ms 2808 KB Correct answer: answer = 10267
103 Correct 8 ms 3064 KB Correct answer: answer = 2582408
104 Correct 6 ms 2936 KB Correct answer: answer = 78024964781
105 Correct 6 ms 2936 KB Correct answer: answer = 9866346457
106 Correct 6 ms 2936 KB Correct answer: answer = 3327720949
107 Correct 6 ms 2936 KB Correct answer: answer = 86064128360
108 Correct 6 ms 2936 KB Correct answer: answer = 12698259150
109 Correct 8 ms 3064 KB Correct answer: answer = 1185259288
110 Correct 24 ms 4852 KB Correct answer: answer = 999889968863
111 Correct 24 ms 4788 KB Correct answer: answer = 999861384931
112 Correct 24 ms 4724 KB Correct answer: answer = 999811809929
113 Correct 24 ms 4724 KB Correct answer: answer = 999869756441
114 Correct 56 ms 6576 KB Correct answer: answer = 1700000000
115 Correct 59 ms 6512 KB Correct answer: answer = 131666670
116 Correct 19 ms 4088 KB Correct answer: answer = 89478486
117 Correct 20 ms 4088 KB Correct answer: answer = 4971040
118 Correct 23 ms 4084 KB Correct answer: answer = 2711494
119 Correct 51 ms 6640 KB Correct answer: answer = 25252530
120 Correct 46 ms 6512 KB Correct answer: answer = 62500000
121 Correct 72 ms 6640 KB Correct answer: answer = 333175097780
122 Correct 74 ms 6640 KB Correct answer: answer = 33121180179
123 Correct 74 ms 6628 KB Correct answer: answer = 9802314015
124 Correct 51 ms 6640 KB Correct answer: answer = 32567551
125 Correct 51 ms 6640 KB Correct answer: answer = 997525000000
126 Correct 70 ms 6384 KB Correct answer: answer = 752723538884
127 Correct 17 ms 4724 KB Correct answer: answer = 1000000000000
128 Correct 24 ms 4852 KB Correct answer: answer = 999978000121
129 Correct 24 ms 4852 KB Correct answer: answer = 745986144735
130 Correct 14 ms 4340 KB Correct answer: answer = 2
131 Correct 52 ms 6520 KB Correct answer: answer = 277966670
132 Correct 53 ms 6512 KB Correct answer: answer = 2500900082
133 Correct 31 ms 4848 KB Correct answer: answer = 301248349636
134 Correct 38 ms 4724 KB Correct answer: answer = 14118891
135 Correct 27 ms 4728 KB Correct answer: answer = 14384977265
136 Correct 26 ms 4824 KB Correct answer: answer = 3681368330
137 Correct 26 ms 4852 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct answer: answer = 4
2 Correct 4 ms 2680 KB Correct answer: answer = 4
3 Correct 4 ms 2680 KB Correct answer: answer = 4
4 Correct 4 ms 2680 KB Correct answer: answer = 12
5 Correct 4 ms 2680 KB Correct answer: answer = 52
6 Correct 4 ms 2808 KB Correct answer: answer = 210
7 Correct 4 ms 2680 KB Correct answer: answer = 88
8 Correct 4 ms 2680 KB Correct answer: answer = 7696
9 Correct 4 ms 2680 KB Correct answer: answer = 1
10 Correct 4 ms 2680 KB Correct answer: answer = 2374
11 Correct 4 ms 2728 KB Correct answer: answer = 9502
12 Correct 4 ms 2680 KB Correct answer: answer = 49
13 Correct 4 ms 2680 KB Correct answer: answer = 151
14 Correct 4 ms 2680 KB Correct answer: answer = 7550
15 Correct 4 ms 2680 KB Correct answer: answer = 7220
16 Correct 4 ms 2680 KB Correct answer: answer = 7550
17 Correct 4 ms 2680 KB Correct answer: answer = 10000
18 Correct 4 ms 2680 KB Correct answer: answer = 10000
19 Correct 4 ms 2680 KB Correct answer: answer = 624
20 Correct 4 ms 2680 KB Correct answer: answer = 10000
21 Correct 4 ms 2680 KB Correct answer: answer = 1
22 Correct 4 ms 2680 KB Correct answer: answer = 4
23 Correct 5 ms 2680 KB Correct answer: answer = 1
24 Correct 4 ms 2680 KB Correct answer: answer = 5
25 Correct 4 ms 2680 KB Correct answer: answer = 41
26 Correct 4 ms 2680 KB Correct answer: answer = 71923
27 Correct 4 ms 2680 KB Correct answer: answer = 77137
28 Correct 5 ms 2808 KB Correct answer: answer = 764
29 Correct 5 ms 2808 KB Correct answer: answer = 250000
30 Correct 4 ms 2808 KB Correct answer: answer = 500
31 Correct 4 ms 2680 KB Correct answer: answer = 32
32 Correct 4 ms 2808 KB Correct answer: answer = 130050
33 Correct 4 ms 2680 KB Correct answer: answer = 5110
34 Correct 4 ms 2680 KB Correct answer: answer = 2626
35 Correct 4 ms 2680 KB Correct answer: answer = 796
36 Correct 4 ms 2808 KB Correct answer: answer = 7580
37 Correct 4 ms 2808 KB Correct answer: answer = 1904
38 Correct 5 ms 2808 KB Correct answer: answer = 996004
39 Correct 4 ms 2808 KB Correct answer: answer = 38817
40 Correct 4 ms 2808 KB Correct answer: answer = 4096
41 Correct 4 ms 2680 KB Correct answer: answer = 1
42 Correct 5 ms 2680 KB Correct answer: answer = 1
43 Correct 5 ms 2808 KB Correct answer: answer = 2040
44 Correct 4 ms 2680 KB Correct answer: answer = 2
45 Correct 4 ms 2684 KB Correct answer: answer = 4
46 Correct 4 ms 2680 KB Correct answer: answer = 9
47 Correct 4 ms 2680 KB Correct answer: answer = 9
48 Correct 4 ms 2680 KB Correct answer: answer = 21
49 Correct 4 ms 2680 KB Correct answer: answer = 71
50 Correct 4 ms 2680 KB Correct answer: answer = 77
51 Correct 4 ms 2680 KB Correct answer: answer = 400
52 Correct 4 ms 2680 KB Correct answer: answer = 996004
53 Correct 4 ms 2680 KB Correct answer: answer = 997310
54 Correct 4 ms 2680 KB Correct answer: answer = 990781
55 Correct 4 ms 2680 KB Correct answer: answer = 996545
56 Correct 4 ms 2808 KB Correct answer: answer = 484
57 Correct 4 ms 2680 KB Correct answer: answer = 484
58 Correct 4 ms 2808 KB Correct answer: answer = 63501
59 Correct 5 ms 2808 KB Correct answer: answer = 323501
60 Correct 5 ms 2808 KB Correct answer: answer = 752500
61 Correct 5 ms 2680 KB Correct answer: answer = 761480
62 Correct 4 ms 2808 KB Correct answer: answer = 758932
63 Correct 4 ms 2680 KB Correct answer: answer = 1000000
64 Correct 4 ms 2808 KB Correct answer: answer = 750500
65 Correct 4 ms 2808 KB Correct answer: answer = 1000000
66 Correct 4 ms 2808 KB Correct answer: answer = 250000
67 Correct 4 ms 2764 KB Correct answer: answer = 250000
68 Correct 3 ms 2680 KB Correct answer: answer = 1000000
69 Correct 4 ms 2680 KB Correct answer: answer = 994009
70 Correct 8 ms 2808 KB Correct answer: answer = 59315
71 Correct 5 ms 2808 KB Correct answer: answer = 25454
72 Correct 5 ms 2680 KB Correct answer: answer = 1504
73 Correct 5 ms 2680 KB Correct answer: answer = 37486
74 Correct 4 ms 2680 KB Correct answer: answer = 4284
75 Correct 4 ms 2680 KB Correct answer: answer = 158008
76 Correct 4 ms 2680 KB Correct answer: answer = 51860
77 Correct 4 ms 2680 KB Correct answer: answer = 12985
78 Correct 6 ms 2812 KB Correct answer: answer = 997864126212
79 Correct 6 ms 2936 KB Correct answer: answer = 998608411647
80 Correct 6 ms 2812 KB Correct answer: answer = 995265560477
81 Correct 8 ms 3064 KB Correct answer: answer = 10125000
82 Correct 0 ms 3064 KB Correct answer: answer = 2291668
83 Correct 7 ms 2808 KB Correct answer: answer = 42388
84 Correct 7 ms 2808 KB Correct answer: answer = 10318
85 Correct 7 ms 2936 KB Correct answer: answer = 3416
86 Correct 15 ms 3064 KB Correct answer: answer = 331708193881
87 Correct 9 ms 3064 KB Correct answer: answer = 2861193756
88 Correct 10 ms 3064 KB Correct answer: answer = 114646930
89 Correct 8 ms 2936 KB Correct answer: answer = 9280921
90 Correct 8 ms 3064 KB Correct answer: answer = 999984053400
91 Correct 9 ms 3064 KB Correct answer: answer = 750935949134
92 Correct 5 ms 2936 KB Correct answer: answer = 1000000000000
93 Correct 5 ms 2808 KB Correct answer: answer = 998762383161
94 Correct 10 ms 3064 KB Correct answer: answer = 23017412908
95 Correct 8 ms 2936 KB Correct answer: answer = 728143410622
96 Correct 5 ms 2896 KB Correct answer: answer = 2
97 Correct 8 ms 3064 KB Correct answer: answer = 1824916
98 Correct 8 ms 3064 KB Correct answer: answer = 10680029
99 Correct 8 ms 3064 KB Correct answer: answer = 18351700
100 Correct 8 ms 3064 KB Correct answer: answer = 16040026
101 Correct 6 ms 2936 KB Correct answer: answer = 253968628325
102 Correct 4 ms 2808 KB Correct answer: answer = 10267
103 Correct 8 ms 3064 KB Correct answer: answer = 2582408
104 Correct 6 ms 2936 KB Correct answer: answer = 78024964781
105 Correct 6 ms 2936 KB Correct answer: answer = 9866346457
106 Correct 6 ms 2936 KB Correct answer: answer = 3327720949
107 Correct 6 ms 2936 KB Correct answer: answer = 86064128360
108 Correct 6 ms 2936 KB Correct answer: answer = 12698259150
109 Correct 8 ms 3064 KB Correct answer: answer = 1185259288
110 Correct 24 ms 4852 KB Correct answer: answer = 999889968863
111 Correct 24 ms 4788 KB Correct answer: answer = 999861384931
112 Correct 24 ms 4724 KB Correct answer: answer = 999811809929
113 Correct 24 ms 4724 KB Correct answer: answer = 999869756441
114 Correct 56 ms 6576 KB Correct answer: answer = 1700000000
115 Correct 59 ms 6512 KB Correct answer: answer = 131666670
116 Correct 19 ms 4088 KB Correct answer: answer = 89478486
117 Correct 20 ms 4088 KB Correct answer: answer = 4971040
118 Correct 23 ms 4084 KB Correct answer: answer = 2711494
119 Correct 51 ms 6640 KB Correct answer: answer = 25252530
120 Correct 46 ms 6512 KB Correct answer: answer = 62500000
121 Correct 72 ms 6640 KB Correct answer: answer = 333175097780
122 Correct 74 ms 6640 KB Correct answer: answer = 33121180179
123 Correct 74 ms 6628 KB Correct answer: answer = 9802314015
124 Correct 51 ms 6640 KB Correct answer: answer = 32567551
125 Correct 51 ms 6640 KB Correct answer: answer = 997525000000
126 Correct 70 ms 6384 KB Correct answer: answer = 752723538884
127 Correct 17 ms 4724 KB Correct answer: answer = 1000000000000
128 Correct 24 ms 4852 KB Correct answer: answer = 999978000121
129 Correct 24 ms 4852 KB Correct answer: answer = 745986144735
130 Correct 14 ms 4340 KB Correct answer: answer = 2
131 Correct 52 ms 6520 KB Correct answer: answer = 277966670
132 Correct 53 ms 6512 KB Correct answer: answer = 2500900082
133 Correct 31 ms 4848 KB Correct answer: answer = 301248349636
134 Correct 38 ms 4724 KB Correct answer: answer = 14118891
135 Correct 27 ms 4728 KB Correct answer: answer = 14384977265
136 Correct 26 ms 4824 KB Correct answer: answer = 3681368330
137 Correct 26 ms 4852 KB Correct answer: answer = 2720316816
138 Correct 47 ms 6768 KB Correct answer: answer = 999976000144
139 Correct 45 ms 6716 KB Correct answer: answer = 999856102410
140 Correct 45 ms 6896 KB Correct answer: answer = 999958401531
141 Correct 45 ms 6780 KB Correct answer: answer = 999769649944
142 Correct 44 ms 6768 KB Correct answer: answer = 999874525918
143 Correct 108 ms 10348 KB Correct answer: answer = 6050000000
144 Correct 115 ms 10324 KB Correct answer: answer = 1112500000
145 Correct 62 ms 7696 KB Correct answer: answer = 4294967296
146 Correct 65 ms 7792 KB Correct answer: answer = 87652406
147 Correct 66 ms 7664 KB Correct answer: answer = 6297664
148 Correct 61 ms 7792 KB Correct answer: answer = 196612
149 Correct 97 ms 10292 KB Correct answer: answer = 15015100
150 Correct 87 ms 10348 KB Correct answer: answer = 25000000
151 Correct 139 ms 10220 KB Correct answer: answer = 333230209550
152 Correct 150 ms 10348 KB Correct answer: answer = 917123769
153 Correct 85 ms 10220 KB Correct answer: answer = 95162
154 Correct 105 ms 10276 KB Correct answer: answer = 382616191
155 Correct 98 ms 10320 KB Correct answer: answer = 990033333400
156 Correct 80 ms 10348 KB Correct answer: answer = 990000100000
157 Correct 124 ms 9800 KB Correct answer: answer = 749998188180
158 Correct 31 ms 6772 KB Correct answer: answer = 1000000000000
159 Correct 44 ms 6768 KB Correct answer: answer = 999988000036
160 Correct 44 ms 6768 KB Correct answer: answer = 744929274393
161 Correct 24 ms 5976 KB Correct answer: answer = 2
162 Correct 82 ms 10220 KB Correct answer: answer = 1300024
163 Correct 106 ms 10348 KB Correct answer: answer = 5000700010
164 Correct 55 ms 6868 KB Correct answer: answer = 354997100800
165 Correct 67 ms 6640 KB Correct answer: answer = 257000
166 Correct 57 ms 6640 KB Correct answer: answer = 3765323
167 Correct 59 ms 6608 KB Correct answer: answer = 1525903
168 Correct 45 ms 6900 KB Correct answer: answer = 67618137730
169 Correct 45 ms 6768 KB Correct answer: answer = 12656680171
170 Correct 47 ms 6768 KB Correct answer: answer = 579831736
171 Correct 71 ms 7660 KB Correct answer: answer = 23605611
172 Correct 45 ms 6716 KB Correct answer: answer = 7052481200
173 Correct 48 ms 6992 KB Correct answer: answer = 1314039500
174 Correct 55 ms 7276 KB Correct answer: answer = 302484000
175 Correct 89 ms 9040 KB Correct answer: answer = 52348480