oj.uz

Submission #540906

# Submission time Handle Problem Language Result Execution time Memory
540906 2022-03-21T23:41:57 Z keta_tsimakuridze Aliens (IOI16_aliens) C++14
100 / 100
 1956 ms 124828 KB 
#include "aliens.h"

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
using namespace std;
const ll N = 1e6 + 5;
ll n, m, cntL[N], cntR[N], R[N];
pii dp[N];
vector<ll> st[N], new_[N];
struct line{
	ll k, b, cn;
};
double _(line a, line b) {
	// a.k * x + a.b = b.k * x + 
	return (double)(a.b - b.b) / (b.k - a.k);
}
ll f(line c, ll x) {
	return ((ll)c.k * x + c.b);
}
ll check(ll c) {
	deque<line> dq;
	ll mx = 0;
	for(ll x = 1; x <= n; x++) {
		dp[x] = {n * n + 5, 0};
		if(cntL[x - 1] + cntR[x + 1] == m) dp[x] = dp[x - 1];
		for(ll j = 0; j < new_[x].size(); j++) {
			ll l = new_[x][j];
			line a;
			ll r = R[l - 1];
			a.b = dp[r].f - (ll)(r - l + 1) * (r - l + 1) + (ll)l * l + 1 - 2 * l;
			a.k = -l; mx = max(mx, l);
			assert(mx == l);
			a.cn = -dp[r].s;
			
			while(dq.size() >= 2) {
				line cur = dq.back();
				line prev = dq[(ll)dq.size() - 2];
				if(_(cur, prev) >= _(prev, a)) dq.pop_back();
				else if(_(cur, prev) == _(prev, a) && cur.cn <= a.cn) dq.pop_back();
				else break;
			} 
			
			dq.push_back(a);
		}
		
		while(dq.size() >= 2) {
			line cur = dq[0];
			line nxt = dq[1];
			if(f(nxt, 2 * x) < f(cur, 2 * x)) dq.pop_front();
			else if(f(nxt, 2 * x) == f(cur, 2 * x) && nxt.cn >= cur.cn) dq.pop_front();
			else break;
		}
		
		
		if(dq.size()) {
			ll y = f(dq[0], 2 * x)  + (ll)x * x + 2 * x  + c;
			dp[x] = min(dp[x], {y, -(dq[0].cn + 1)});
		}
	}
	
	return -dp[n].s;
}
long long take_photos(int N, int M, int k, std::vector<int> r1, std::vector<int> c) {
	swap(N, M); 
	m = M; n = N;
//	vector<ll> l(m + 5);
	ll mnl = n, mxr = 0;
    for(ll i = 0; i < m; i++) {
    	if(c[i] > r1[i]) swap(c[i], r1[i]);
    	ll l = min(r1[i], c[i]); r1[i] = max(r1[i], c[i]);
    	l++; r1[i]++;
    	cntL[r1[i]]++; cntR[l]++;
    	st[l].push_back(r1[i]);
    	mnl = min(l, (ll)mnl); mxr = max(mxr, (ll)r1[i]);
	}
	if(k == 1) {
		return (ll)(mxr - mnl + 1) * (mxr - mnl + 1);
	}
	for(ll i = 1; i <= n; i++) cntL[i] += cntL[i - 1];
	for(ll i = n; i >= 1; i--) cntR[i] += cntR[i + 1];
	ll C = 0;
	for(ll i = 1; i <= n; i++) {
		C = max(C, i);
		for(ll j = 0;j < st[i].size(); j++) {
			C = max(C, st[i][j]);
		}
		R[i] = C;
		new_[R[i - 1] + 1].push_back(i);
	}
	ll l = 0, r = 1e13, p = 0;
	while(l <= r) {
		ll mid = (l + r) / 2;
		if(check(mid) >= k) {
			p = mid;
			l = mid + 1;
			
		} else r = mid - 1;
	}
	check(p); 
	return dp[n].f - (ll)p * k;
}

Compilation message

aliens.cpp: In function 'long long int check(long long int)':
aliens.cpp:29:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(ll j = 0; j < new_[x].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:87:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(ll j = 0;j < st[i].size(); j++) {
      |                ~~^~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47188 KB Correct answer: answer = 4
2 Correct 25 ms 47284 KB Correct answer: answer = 4
3 Correct 26 ms 47276 KB Correct answer: answer = 4
4 Correct 24 ms 47196 KB Correct answer: answer = 12
5 Correct 23 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47188 KB Correct answer: answer = 210
7 Correct 22 ms 47188 KB Correct answer: answer = 88
8 Correct 24 ms 47236 KB Correct answer: answer = 7696
9 Correct 23 ms 47232 KB Correct answer: answer = 1
10 Correct 24 ms 47260 KB Correct answer: answer = 2374
11 Correct 25 ms 47208 KB Correct answer: answer = 9502
12 Correct 23 ms 47232 KB Correct answer: answer = 49
13 Correct 25 ms 47292 KB Correct answer: answer = 151
14 Correct 22 ms 47220 KB Correct answer: answer = 7550
15 Correct 24 ms 47172 KB Correct answer: answer = 7220
16 Correct 23 ms 47188 KB Correct answer: answer = 7550
17 Correct 26 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47188 KB Correct answer: answer = 10000
19 Correct 23 ms 47188 KB Correct answer: answer = 624
20 Correct 23 ms 47232 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47268 KB Correct answer: answer = 1
2 Correct 27 ms 47216 KB Correct answer: answer = 4
3 Correct 24 ms 47188 KB Correct answer: answer = 1
4 Correct 25 ms 47284 KB Correct answer: answer = 5
5 Correct 25 ms 47288 KB Correct answer: answer = 41
6 Correct 24 ms 47308 KB Correct answer: answer = 71923
7 Correct 25 ms 47316 KB Correct answer: answer = 77137
8 Correct 26 ms 47316 KB Correct answer: answer = 764
9 Correct 23 ms 47304 KB Correct answer: answer = 250000
10 Correct 26 ms 47316 KB Correct answer: answer = 500
11 Correct 24 ms 47188 KB Correct answer: answer = 32
12 Correct 25 ms 47296 KB Correct answer: answer = 130050
13 Correct 24 ms 47280 KB Correct answer: answer = 5110
14 Correct 25 ms 47344 KB Correct answer: answer = 2626
15 Correct 24 ms 47324 KB Correct answer: answer = 796
16 Correct 23 ms 47440 KB Correct answer: answer = 7580
17 Correct 23 ms 47280 KB Correct answer: answer = 1904
18 Correct 24 ms 47236 KB Correct answer: answer = 996004
19 Correct 25 ms 47368 KB Correct answer: answer = 38817
20 Correct 32 ms 47292 KB Correct answer: answer = 4096
21 Correct 23 ms 47188 KB Correct answer: answer = 1
22 Correct 25 ms 47268 KB Correct answer: answer = 1
23 Correct 24 ms 47364 KB Correct answer: answer = 2040
24 Correct 25 ms 47292 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47188 KB Correct answer: answer = 4
2 Correct 25 ms 47284 KB Correct answer: answer = 4
3 Correct 26 ms 47276 KB Correct answer: answer = 4
4 Correct 24 ms 47196 KB Correct answer: answer = 12
5 Correct 23 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47188 KB Correct answer: answer = 210
7 Correct 22 ms 47188 KB Correct answer: answer = 88
8 Correct 24 ms 47236 KB Correct answer: answer = 7696
9 Correct 23 ms 47232 KB Correct answer: answer = 1
10 Correct 24 ms 47260 KB Correct answer: answer = 2374
11 Correct 25 ms 47208 KB Correct answer: answer = 9502
12 Correct 23 ms 47232 KB Correct answer: answer = 49
13 Correct 25 ms 47292 KB Correct answer: answer = 151
14 Correct 22 ms 47220 KB Correct answer: answer = 7550
15 Correct 24 ms 47172 KB Correct answer: answer = 7220
16 Correct 23 ms 47188 KB Correct answer: answer = 7550
17 Correct 26 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47188 KB Correct answer: answer = 10000
19 Correct 23 ms 47188 KB Correct answer: answer = 624
20 Correct 23 ms 47232 KB Correct answer: answer = 10000
21 Correct 23 ms 47268 KB Correct answer: answer = 1
22 Correct 27 ms 47216 KB Correct answer: answer = 4
23 Correct 24 ms 47188 KB Correct answer: answer = 1
24 Correct 25 ms 47284 KB Correct answer: answer = 5
25 Correct 25 ms 47288 KB Correct answer: answer = 41
26 Correct 24 ms 47308 KB Correct answer: answer = 71923
27 Correct 25 ms 47316 KB Correct answer: answer = 77137
28 Correct 26 ms 47316 KB Correct answer: answer = 764
29 Correct 23 ms 47304 KB Correct answer: answer = 250000
30 Correct 26 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47188 KB Correct answer: answer = 32
32 Correct 25 ms 47296 KB Correct answer: answer = 130050
33 Correct 24 ms 47280 KB Correct answer: answer = 5110
34 Correct 25 ms 47344 KB Correct answer: answer = 2626
35 Correct 24 ms 47324 KB Correct answer: answer = 796
36 Correct 23 ms 47440 KB Correct answer: answer = 7580
37 Correct 23 ms 47280 KB Correct answer: answer = 1904
38 Correct 24 ms 47236 KB Correct answer: answer = 996004
39 Correct 25 ms 47368 KB Correct answer: answer = 38817
40 Correct 32 ms 47292 KB Correct answer: answer = 4096
41 Correct 23 ms 47188 KB Correct answer: answer = 1
42 Correct 25 ms 47268 KB Correct answer: answer = 1
43 Correct 24 ms 47364 KB Correct answer: answer = 2040
44 Correct 25 ms 47292 KB Correct answer: answer = 2
45 Correct 23 ms 47256 KB Correct answer: answer = 4
46 Correct 23 ms 47304 KB Correct answer: answer = 9
47 Correct 24 ms 47188 KB Correct answer: answer = 9
48 Correct 24 ms 47264 KB Correct answer: answer = 21
49 Correct 24 ms 47188 KB Correct answer: answer = 71
50 Correct 24 ms 47288 KB Correct answer: answer = 77
51 Correct 23 ms 47188 KB Correct answer: answer = 400
52 Correct 22 ms 47292 KB Correct answer: answer = 996004
53 Correct 23 ms 47308 KB Correct answer: answer = 997310
54 Correct 23 ms 47316 KB Correct answer: answer = 990781
55 Correct 24 ms 47256 KB Correct answer: answer = 996545
56 Correct 23 ms 47188 KB Correct answer: answer = 484
57 Correct 23 ms 47232 KB Correct answer: answer = 484
58 Correct 24 ms 47292 KB Correct answer: answer = 63501
59 Correct 24 ms 47316 KB Correct answer: answer = 323501
60 Correct 24 ms 47312 KB Correct answer: answer = 752500
61 Correct 25 ms 47316 KB Correct answer: answer = 761480
62 Correct 24 ms 47344 KB Correct answer: answer = 758932
63 Correct 22 ms 47316 KB Correct answer: answer = 1000000
64 Correct 24 ms 47380 KB Correct answer: answer = 750500
65 Correct 23 ms 47244 KB Correct answer: answer = 1000000
66 Correct 26 ms 47304 KB Correct answer: answer = 250000
67 Correct 25 ms 47248 KB Correct answer: answer = 250000
68 Correct 24 ms 47348 KB Correct answer: answer = 1000000
69 Correct 24 ms 47208 KB Correct answer: answer = 994009
70 Correct 25 ms 47376 KB Correct answer: answer = 59315
71 Correct 24 ms 47316 KB Correct answer: answer = 25454
72 Correct 23 ms 47256 KB Correct answer: answer = 1504
73 Correct 25 ms 47336 KB Correct answer: answer = 37486
74 Correct 25 ms 47340 KB Correct answer: answer = 4284
75 Correct 25 ms 47316 KB Correct answer: answer = 158008
76 Correct 25 ms 47340 KB Correct answer: answer = 51860
77 Correct 24 ms 47276 KB Correct answer: answer = 12985

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47188 KB Correct answer: answer = 4
2 Correct 25 ms 47284 KB Correct answer: answer = 4
3 Correct 26 ms 47276 KB Correct answer: answer = 4
4 Correct 24 ms 47196 KB Correct answer: answer = 12
5 Correct 23 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47188 KB Correct answer: answer = 210
7 Correct 22 ms 47188 KB Correct answer: answer = 88
8 Correct 24 ms 47236 KB Correct answer: answer = 7696
9 Correct 23 ms 47232 KB Correct answer: answer = 1
10 Correct 24 ms 47260 KB Correct answer: answer = 2374
11 Correct 25 ms 47208 KB Correct answer: answer = 9502
12 Correct 23 ms 47232 KB Correct answer: answer = 49
13 Correct 25 ms 47292 KB Correct answer: answer = 151
14 Correct 22 ms 47220 KB Correct answer: answer = 7550
15 Correct 24 ms 47172 KB Correct answer: answer = 7220
16 Correct 23 ms 47188 KB Correct answer: answer = 7550
17 Correct 26 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47188 KB Correct answer: answer = 10000
19 Correct 23 ms 47188 KB Correct answer: answer = 624
20 Correct 23 ms 47232 KB Correct answer: answer = 10000
21 Correct 23 ms 47268 KB Correct answer: answer = 1
22 Correct 27 ms 47216 KB Correct answer: answer = 4
23 Correct 24 ms 47188 KB Correct answer: answer = 1
24 Correct 25 ms 47284 KB Correct answer: answer = 5
25 Correct 25 ms 47288 KB Correct answer: answer = 41
26 Correct 24 ms 47308 KB Correct answer: answer = 71923
27 Correct 25 ms 47316 KB Correct answer: answer = 77137
28 Correct 26 ms 47316 KB Correct answer: answer = 764
29 Correct 23 ms 47304 KB Correct answer: answer = 250000
30 Correct 26 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47188 KB Correct answer: answer = 32
32 Correct 25 ms 47296 KB Correct answer: answer = 130050
33 Correct 24 ms 47280 KB Correct answer: answer = 5110
34 Correct 25 ms 47344 KB Correct answer: answer = 2626
35 Correct 24 ms 47324 KB Correct answer: answer = 796
36 Correct 23 ms 47440 KB Correct answer: answer = 7580
37 Correct 23 ms 47280 KB Correct answer: answer = 1904
38 Correct 24 ms 47236 KB Correct answer: answer = 996004
39 Correct 25 ms 47368 KB Correct answer: answer = 38817
40 Correct 32 ms 47292 KB Correct answer: answer = 4096
41 Correct 23 ms 47188 KB Correct answer: answer = 1
42 Correct 25 ms 47268 KB Correct answer: answer = 1
43 Correct 24 ms 47364 KB Correct answer: answer = 2040
44 Correct 25 ms 47292 KB Correct answer: answer = 2
45 Correct 23 ms 47256 KB Correct answer: answer = 4
46 Correct 23 ms 47304 KB Correct answer: answer = 9
47 Correct 24 ms 47188 KB Correct answer: answer = 9
48 Correct 24 ms 47264 KB Correct answer: answer = 21
49 Correct 24 ms 47188 KB Correct answer: answer = 71
50 Correct 24 ms 47288 KB Correct answer: answer = 77
51 Correct 23 ms 47188 KB Correct answer: answer = 400
52 Correct 22 ms 47292 KB Correct answer: answer = 996004
53 Correct 23 ms 47308 KB Correct answer: answer = 997310
54 Correct 23 ms 47316 KB Correct answer: answer = 990781
55 Correct 24 ms 47256 KB Correct answer: answer = 996545
56 Correct 23 ms 47188 KB Correct answer: answer = 484
57 Correct 23 ms 47232 KB Correct answer: answer = 484
58 Correct 24 ms 47292 KB Correct answer: answer = 63501
59 Correct 24 ms 47316 KB Correct answer: answer = 323501
60 Correct 24 ms 47312 KB Correct answer: answer = 752500
61 Correct 25 ms 47316 KB Correct answer: answer = 761480
62 Correct 24 ms 47344 KB Correct answer: answer = 758932
63 Correct 22 ms 47316 KB Correct answer: answer = 1000000
64 Correct 24 ms 47380 KB Correct answer: answer = 750500
65 Correct 23 ms 47244 KB Correct answer: answer = 1000000
66 Correct 26 ms 47304 KB Correct answer: answer = 250000
67 Correct 25 ms 47248 KB Correct answer: answer = 250000
68 Correct 24 ms 47348 KB Correct answer: answer = 1000000
69 Correct 24 ms 47208 KB Correct answer: answer = 994009
70 Correct 25 ms 47376 KB Correct answer: answer = 59315
71 Correct 24 ms 47316 KB Correct answer: answer = 25454
72 Correct 23 ms 47256 KB Correct answer: answer = 1504
73 Correct 25 ms 47336 KB Correct answer: answer = 37486
74 Correct 25 ms 47340 KB Correct answer: answer = 4284
75 Correct 25 ms 47316 KB Correct answer: answer = 158008
76 Correct 25 ms 47340 KB Correct answer: answer = 51860
77 Correct 24 ms 47276 KB Correct answer: answer = 12985
78 Correct 1188 ms 94488 KB Correct answer: answer = 997864126212
79 Correct 1129 ms 95540 KB Correct answer: answer = 998608411647
80 Correct 1117 ms 94704 KB Correct answer: answer = 995265560477
81 Correct 35 ms 47828 KB Correct answer: answer = 10125000
82 Correct 31 ms 47808 KB Correct answer: answer = 2291668
83 Correct 29 ms 47504 KB Correct answer: answer = 42388
84 Correct 27 ms 47464 KB Correct answer: answer = 10318
85 Correct 27 ms 47580 KB Correct answer: answer = 3416
86 Correct 1956 ms 117936 KB Correct answer: answer = 331708193881
87 Correct 1555 ms 117936 KB Correct answer: answer = 2861193756
88 Correct 1459 ms 118040 KB Correct answer: answer = 114646930
89 Correct 31 ms 47828 KB Correct answer: answer = 9280921
90 Correct 522 ms 94568 KB Correct answer: answer = 999984053400
91 Correct 1257 ms 96340 KB Correct answer: answer = 750935949134
92 Correct 521 ms 94588 KB Correct answer: answer = 1000000000000
93 Correct 1112 ms 94508 KB Correct answer: answer = 998762383161
94 Correct 1630 ms 116744 KB Correct answer: answer = 23017412908
95 Correct 1176 ms 95092 KB Correct answer: answer = 728143410622
96 Correct 1322 ms 117872 KB Correct answer: answer = 2
97 Correct 1226 ms 118080 KB Correct answer: answer = 1824916
98 Correct 201 ms 54564 KB Correct answer: answer = 10680029
99 Correct 175 ms 54456 KB Correct answer: answer = 18351700
100 Correct 1298 ms 117880 KB Correct answer: answer = 16040026
101 Correct 1206 ms 106040 KB Correct answer: answer = 253968628325
102 Correct 31 ms 47512 KB Correct answer: answer = 10267
103 Correct 758 ms 83244 KB Correct answer: answer = 2582408
104 Correct 1245 ms 109220 KB Correct answer: answer = 78024964781
105 Correct 1227 ms 111816 KB Correct answer: answer = 9866346457
106 Correct 1299 ms 107388 KB Correct answer: answer = 3327720949
107 Correct 1214 ms 96088 KB Correct answer: answer = 86064128360
108 Correct 1226 ms 97612 KB Correct answer: answer = 12698259150
109 Correct 1343 ms 100556 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47188 KB Correct answer: answer = 4
2 Correct 25 ms 47284 KB Correct answer: answer = 4
3 Correct 26 ms 47276 KB Correct answer: answer = 4
4 Correct 24 ms 47196 KB Correct answer: answer = 12
5 Correct 23 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47188 KB Correct answer: answer = 210
7 Correct 22 ms 47188 KB Correct answer: answer = 88
8 Correct 24 ms 47236 KB Correct answer: answer = 7696
9 Correct 23 ms 47232 KB Correct answer: answer = 1
10 Correct 24 ms 47260 KB Correct answer: answer = 2374
11 Correct 25 ms 47208 KB Correct answer: answer = 9502
12 Correct 23 ms 47232 KB Correct answer: answer = 49
13 Correct 25 ms 47292 KB Correct answer: answer = 151
14 Correct 22 ms 47220 KB Correct answer: answer = 7550
15 Correct 24 ms 47172 KB Correct answer: answer = 7220
16 Correct 23 ms 47188 KB Correct answer: answer = 7550
17 Correct 26 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47188 KB Correct answer: answer = 10000
19 Correct 23 ms 47188 KB Correct answer: answer = 624
20 Correct 23 ms 47232 KB Correct answer: answer = 10000
21 Correct 23 ms 47268 KB Correct answer: answer = 1
22 Correct 27 ms 47216 KB Correct answer: answer = 4
23 Correct 24 ms 47188 KB Correct answer: answer = 1
24 Correct 25 ms 47284 KB Correct answer: answer = 5
25 Correct 25 ms 47288 KB Correct answer: answer = 41
26 Correct 24 ms 47308 KB Correct answer: answer = 71923
27 Correct 25 ms 47316 KB Correct answer: answer = 77137
28 Correct 26 ms 47316 KB Correct answer: answer = 764
29 Correct 23 ms 47304 KB Correct answer: answer = 250000
30 Correct 26 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47188 KB Correct answer: answer = 32
32 Correct 25 ms 47296 KB Correct answer: answer = 130050
33 Correct 24 ms 47280 KB Correct answer: answer = 5110
34 Correct 25 ms 47344 KB Correct answer: answer = 2626
35 Correct 24 ms 47324 KB Correct answer: answer = 796
36 Correct 23 ms 47440 KB Correct answer: answer = 7580
37 Correct 23 ms 47280 KB Correct answer: answer = 1904
38 Correct 24 ms 47236 KB Correct answer: answer = 996004
39 Correct 25 ms 47368 KB Correct answer: answer = 38817
40 Correct 32 ms 47292 KB Correct answer: answer = 4096
41 Correct 23 ms 47188 KB Correct answer: answer = 1
42 Correct 25 ms 47268 KB Correct answer: answer = 1
43 Correct 24 ms 47364 KB Correct answer: answer = 2040
44 Correct 25 ms 47292 KB Correct answer: answer = 2
45 Correct 23 ms 47256 KB Correct answer: answer = 4
46 Correct 23 ms 47304 KB Correct answer: answer = 9
47 Correct 24 ms 47188 KB Correct answer: answer = 9
48 Correct 24 ms 47264 KB Correct answer: answer = 21
49 Correct 24 ms 47188 KB Correct answer: answer = 71
50 Correct 24 ms 47288 KB Correct answer: answer = 77
51 Correct 23 ms 47188 KB Correct answer: answer = 400
52 Correct 22 ms 47292 KB Correct answer: answer = 996004
53 Correct 23 ms 47308 KB Correct answer: answer = 997310
54 Correct 23 ms 47316 KB Correct answer: answer = 990781
55 Correct 24 ms 47256 KB Correct answer: answer = 996545
56 Correct 23 ms 47188 KB Correct answer: answer = 484
57 Correct 23 ms 47232 KB Correct answer: answer = 484
58 Correct 24 ms 47292 KB Correct answer: answer = 63501
59 Correct 24 ms 47316 KB Correct answer: answer = 323501
60 Correct 24 ms 47312 KB Correct answer: answer = 752500
61 Correct 25 ms 47316 KB Correct answer: answer = 761480
62 Correct 24 ms 47344 KB Correct answer: answer = 758932
63 Correct 22 ms 47316 KB Correct answer: answer = 1000000
64 Correct 24 ms 47380 KB Correct answer: answer = 750500
65 Correct 23 ms 47244 KB Correct answer: answer = 1000000
66 Correct 26 ms 47304 KB Correct answer: answer = 250000
67 Correct 25 ms 47248 KB Correct answer: answer = 250000
68 Correct 24 ms 47348 KB Correct answer: answer = 1000000
69 Correct 24 ms 47208 KB Correct answer: answer = 994009
70 Correct 25 ms 47376 KB Correct answer: answer = 59315
71 Correct 24 ms 47316 KB Correct answer: answer = 25454
72 Correct 23 ms 47256 KB Correct answer: answer = 1504
73 Correct 25 ms 47336 KB Correct answer: answer = 37486
74 Correct 25 ms 47340 KB Correct answer: answer = 4284
75 Correct 25 ms 47316 KB Correct answer: answer = 158008
76 Correct 25 ms 47340 KB Correct answer: answer = 51860
77 Correct 24 ms 47276 KB Correct answer: answer = 12985
78 Correct 1188 ms 94488 KB Correct answer: answer = 997864126212
79 Correct 1129 ms 95540 KB Correct answer: answer = 998608411647
80 Correct 1117 ms 94704 KB Correct answer: answer = 995265560477
81 Correct 35 ms 47828 KB Correct answer: answer = 10125000
82 Correct 31 ms 47808 KB Correct answer: answer = 2291668
83 Correct 29 ms 47504 KB Correct answer: answer = 42388
84 Correct 27 ms 47464 KB Correct answer: answer = 10318
85 Correct 27 ms 47580 KB Correct answer: answer = 3416
86 Correct 1956 ms 117936 KB Correct answer: answer = 331708193881
87 Correct 1555 ms 117936 KB Correct answer: answer = 2861193756
88 Correct 1459 ms 118040 KB Correct answer: answer = 114646930
89 Correct 31 ms 47828 KB Correct answer: answer = 9280921
90 Correct 522 ms 94568 KB Correct answer: answer = 999984053400
91 Correct 1257 ms 96340 KB Correct answer: answer = 750935949134
92 Correct 521 ms 94588 KB Correct answer: answer = 1000000000000
93 Correct 1112 ms 94508 KB Correct answer: answer = 998762383161
94 Correct 1630 ms 116744 KB Correct answer: answer = 23017412908
95 Correct 1176 ms 95092 KB Correct answer: answer = 728143410622
96 Correct 1322 ms 117872 KB Correct answer: answer = 2
97 Correct 1226 ms 118080 KB Correct answer: answer = 1824916
98 Correct 201 ms 54564 KB Correct answer: answer = 10680029
99 Correct 175 ms 54456 KB Correct answer: answer = 18351700
100 Correct 1298 ms 117880 KB Correct answer: answer = 16040026
101 Correct 1206 ms 106040 KB Correct answer: answer = 253968628325
102 Correct 31 ms 47512 KB Correct answer: answer = 10267
103 Correct 758 ms 83244 KB Correct answer: answer = 2582408
104 Correct 1245 ms 109220 KB Correct answer: answer = 78024964781
105 Correct 1227 ms 111816 KB Correct answer: answer = 9866346457
106 Correct 1299 ms 107388 KB Correct answer: answer = 3327720949
107 Correct 1214 ms 96088 KB Correct answer: answer = 86064128360
108 Correct 1226 ms 97612 KB Correct answer: answer = 12698259150
109 Correct 1343 ms 100556 KB Correct answer: answer = 1185259288
110 Correct 689 ms 97356 KB Correct answer: answer = 999889968863
111 Correct 1163 ms 101356 KB Correct answer: answer = 999861384931
112 Correct 1163 ms 98264 KB Correct answer: answer = 999811809929
113 Correct 588 ms 97464 KB Correct answer: answer = 999869756441
114 Correct 125 ms 54888 KB Correct answer: answer = 1700000000
115 Correct 132 ms 54772 KB Correct answer: answer = 131666670
116 Correct 51 ms 49456 KB Correct answer: answer = 89478486
117 Correct 64 ms 49484 KB Correct answer: answer = 4971040
118 Correct 52 ms 49484 KB Correct answer: answer = 2711494
119 Correct 116 ms 54188 KB Correct answer: answer = 25252530
120 Correct 123 ms 54084 KB Correct answer: answer = 62500000
121 Correct 1704 ms 120704 KB Correct answer: answer = 333175097780
122 Correct 1900 ms 120696 KB Correct answer: answer = 33121180179
123 Correct 1733 ms 120732 KB Correct answer: answer = 9802314015
124 Correct 113 ms 54060 KB Correct answer: answer = 32567551
125 Correct 580 ms 98892 KB Correct answer: answer = 997525000000
126 Correct 1422 ms 99528 KB Correct answer: answer = 752723538884
127 Correct 522 ms 97436 KB Correct answer: answer = 1000000000000
128 Correct 1116 ms 97296 KB Correct answer: answer = 999978000121
129 Correct 1314 ms 98204 KB Correct answer: answer = 745986144735
130 Correct 1347 ms 119084 KB Correct answer: answer = 2
131 Correct 1275 ms 121172 KB Correct answer: answer = 277966670
132 Correct 1305 ms 120664 KB Correct answer: answer = 2500900082
133 Correct 1293 ms 107512 KB Correct answer: answer = 301248349636
134 Correct 102 ms 51024 KB Correct answer: answer = 14118891
135 Correct 1251 ms 116476 KB Correct answer: answer = 14384977265
136 Correct 1275 ms 113088 KB Correct answer: answer = 3681368330
137 Correct 1281 ms 111732 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 47188 KB Correct answer: answer = 4
2 Correct 25 ms 47284 KB Correct answer: answer = 4
3 Correct 26 ms 47276 KB Correct answer: answer = 4
4 Correct 24 ms 47196 KB Correct answer: answer = 12
5 Correct 23 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47188 KB Correct answer: answer = 210
7 Correct 22 ms 47188 KB Correct answer: answer = 88
8 Correct 24 ms 47236 KB Correct answer: answer = 7696
9 Correct 23 ms 47232 KB Correct answer: answer = 1
10 Correct 24 ms 47260 KB Correct answer: answer = 2374
11 Correct 25 ms 47208 KB Correct answer: answer = 9502
12 Correct 23 ms 47232 KB Correct answer: answer = 49
13 Correct 25 ms 47292 KB Correct answer: answer = 151
14 Correct 22 ms 47220 KB Correct answer: answer = 7550
15 Correct 24 ms 47172 KB Correct answer: answer = 7220
16 Correct 23 ms 47188 KB Correct answer: answer = 7550
17 Correct 26 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47188 KB Correct answer: answer = 10000
19 Correct 23 ms 47188 KB Correct answer: answer = 624
20 Correct 23 ms 47232 KB Correct answer: answer = 10000
21 Correct 23 ms 47268 KB Correct answer: answer = 1
22 Correct 27 ms 47216 KB Correct answer: answer = 4
23 Correct 24 ms 47188 KB Correct answer: answer = 1
24 Correct 25 ms 47284 KB Correct answer: answer = 5
25 Correct 25 ms 47288 KB Correct answer: answer = 41
26 Correct 24 ms 47308 KB Correct answer: answer = 71923
27 Correct 25 ms 47316 KB Correct answer: answer = 77137
28 Correct 26 ms 47316 KB Correct answer: answer = 764
29 Correct 23 ms 47304 KB Correct answer: answer = 250000
30 Correct 26 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47188 KB Correct answer: answer = 32
32 Correct 25 ms 47296 KB Correct answer: answer = 130050
33 Correct 24 ms 47280 KB Correct answer: answer = 5110
34 Correct 25 ms 47344 KB Correct answer: answer = 2626
35 Correct 24 ms 47324 KB Correct answer: answer = 796
36 Correct 23 ms 47440 KB Correct answer: answer = 7580
37 Correct 23 ms 47280 KB Correct answer: answer = 1904
38 Correct 24 ms 47236 KB Correct answer: answer = 996004
39 Correct 25 ms 47368 KB Correct answer: answer = 38817
40 Correct 32 ms 47292 KB Correct answer: answer = 4096
41 Correct 23 ms 47188 KB Correct answer: answer = 1
42 Correct 25 ms 47268 KB Correct answer: answer = 1
43 Correct 24 ms 47364 KB Correct answer: answer = 2040
44 Correct 25 ms 47292 KB Correct answer: answer = 2
45 Correct 23 ms 47256 KB Correct answer: answer = 4
46 Correct 23 ms 47304 KB Correct answer: answer = 9
47 Correct 24 ms 47188 KB Correct answer: answer = 9
48 Correct 24 ms 47264 KB Correct answer: answer = 21
49 Correct 24 ms 47188 KB Correct answer: answer = 71
50 Correct 24 ms 47288 KB Correct answer: answer = 77
51 Correct 23 ms 47188 KB Correct answer: answer = 400
52 Correct 22 ms 47292 KB Correct answer: answer = 996004
53 Correct 23 ms 47308 KB Correct answer: answer = 997310
54 Correct 23 ms 47316 KB Correct answer: answer = 990781
55 Correct 24 ms 47256 KB Correct answer: answer = 996545
56 Correct 23 ms 47188 KB Correct answer: answer = 484
57 Correct 23 ms 47232 KB Correct answer: answer = 484
58 Correct 24 ms 47292 KB Correct answer: answer = 63501
59 Correct 24 ms 47316 KB Correct answer: answer = 323501
60 Correct 24 ms 47312 KB Correct answer: answer = 752500
61 Correct 25 ms 47316 KB Correct answer: answer = 761480
62 Correct 24 ms 47344 KB Correct answer: answer = 758932
63 Correct 22 ms 47316 KB Correct answer: answer = 1000000
64 Correct 24 ms 47380 KB Correct answer: answer = 750500
65 Correct 23 ms 47244 KB Correct answer: answer = 1000000
66 Correct 26 ms 47304 KB Correct answer: answer = 250000
67 Correct 25 ms 47248 KB Correct answer: answer = 250000
68 Correct 24 ms 47348 KB Correct answer: answer = 1000000
69 Correct 24 ms 47208 KB Correct answer: answer = 994009
70 Correct 25 ms 47376 KB Correct answer: answer = 59315
71 Correct 24 ms 47316 KB Correct answer: answer = 25454
72 Correct 23 ms 47256 KB Correct answer: answer = 1504
73 Correct 25 ms 47336 KB Correct answer: answer = 37486
74 Correct 25 ms 47340 KB Correct answer: answer = 4284
75 Correct 25 ms 47316 KB Correct answer: answer = 158008
76 Correct 25 ms 47340 KB Correct answer: answer = 51860
77 Correct 24 ms 47276 KB Correct answer: answer = 12985
78 Correct 1188 ms 94488 KB Correct answer: answer = 997864126212
79 Correct 1129 ms 95540 KB Correct answer: answer = 998608411647
80 Correct 1117 ms 94704 KB Correct answer: answer = 995265560477
81 Correct 35 ms 47828 KB Correct answer: answer = 10125000
82 Correct 31 ms 47808 KB Correct answer: answer = 2291668
83 Correct 29 ms 47504 KB Correct answer: answer = 42388
84 Correct 27 ms 47464 KB Correct answer: answer = 10318
85 Correct 27 ms 47580 KB Correct answer: answer = 3416
86 Correct 1956 ms 117936 KB Correct answer: answer = 331708193881
87 Correct 1555 ms 117936 KB Correct answer: answer = 2861193756
88 Correct 1459 ms 118040 KB Correct answer: answer = 114646930
89 Correct 31 ms 47828 KB Correct answer: answer = 9280921
90 Correct 522 ms 94568 KB Correct answer: answer = 999984053400
91 Correct 1257 ms 96340 KB Correct answer: answer = 750935949134
92 Correct 521 ms 94588 KB Correct answer: answer = 1000000000000
93 Correct 1112 ms 94508 KB Correct answer: answer = 998762383161
94 Correct 1630 ms 116744 KB Correct answer: answer = 23017412908
95 Correct 1176 ms 95092 KB Correct answer: answer = 728143410622
96 Correct 1322 ms 117872 KB Correct answer: answer = 2
97 Correct 1226 ms 118080 KB Correct answer: answer = 1824916
98 Correct 201 ms 54564 KB Correct answer: answer = 10680029
99 Correct 175 ms 54456 KB Correct answer: answer = 18351700
100 Correct 1298 ms 117880 KB Correct answer: answer = 16040026
101 Correct 1206 ms 106040 KB Correct answer: answer = 253968628325
102 Correct 31 ms 47512 KB Correct answer: answer = 10267
103 Correct 758 ms 83244 KB Correct answer: answer = 2582408
104 Correct 1245 ms 109220 KB Correct answer: answer = 78024964781
105 Correct 1227 ms 111816 KB Correct answer: answer = 9866346457
106 Correct 1299 ms 107388 KB Correct answer: answer = 3327720949
107 Correct 1214 ms 96088 KB Correct answer: answer = 86064128360
108 Correct 1226 ms 97612 KB Correct answer: answer = 12698259150
109 Correct 1343 ms 100556 KB Correct answer: answer = 1185259288
110 Correct 689 ms 97356 KB Correct answer: answer = 999889968863
111 Correct 1163 ms 101356 KB Correct answer: answer = 999861384931
112 Correct 1163 ms 98264 KB Correct answer: answer = 999811809929
113 Correct 588 ms 97464 KB Correct answer: answer = 999869756441
114 Correct 125 ms 54888 KB Correct answer: answer = 1700000000
115 Correct 132 ms 54772 KB Correct answer: answer = 131666670
116 Correct 51 ms 49456 KB Correct answer: answer = 89478486
117 Correct 64 ms 49484 KB Correct answer: answer = 4971040
118 Correct 52 ms 49484 KB Correct answer: answer = 2711494
119 Correct 116 ms 54188 KB Correct answer: answer = 25252530
120 Correct 123 ms 54084 KB Correct answer: answer = 62500000
121 Correct 1704 ms 120704 KB Correct answer: answer = 333175097780
122 Correct 1900 ms 120696 KB Correct answer: answer = 33121180179
123 Correct 1733 ms 120732 KB Correct answer: answer = 9802314015
124 Correct 113 ms 54060 KB Correct answer: answer = 32567551
125 Correct 580 ms 98892 KB Correct answer: answer = 997525000000
126 Correct 1422 ms 99528 KB Correct answer: answer = 752723538884
127 Correct 522 ms 97436 KB Correct answer: answer = 1000000000000
128 Correct 1116 ms 97296 KB Correct answer: answer = 999978000121
129 Correct 1314 ms 98204 KB Correct answer: answer = 745986144735
130 Correct 1347 ms 119084 KB Correct answer: answer = 2
131 Correct 1275 ms 121172 KB Correct answer: answer = 277966670
132 Correct 1305 ms 120664 KB Correct answer: answer = 2500900082
133 Correct 1293 ms 107512 KB Correct answer: answer = 301248349636
134 Correct 102 ms 51024 KB Correct answer: answer = 14118891
135 Correct 1251 ms 116476 KB Correct answer: answer = 14384977265
136 Correct 1275 ms 113088 KB Correct answer: answer = 3681368330
137 Correct 1281 ms 111732 KB Correct answer: answer = 2720316816
138 Correct 70 ms 68520 KB Correct answer: answer = 999976000144
139 Correct 1180 ms 100248 KB Correct answer: answer = 999856102410
140 Correct 1157 ms 100216 KB Correct answer: answer = 999958401531
141 Correct 1283 ms 104292 KB Correct answer: answer = 999769649944
142 Correct 1175 ms 104216 KB Correct answer: answer = 999874525918
143 Correct 222 ms 61884 KB Correct answer: answer = 6050000000
144 Correct 242 ms 61676 KB Correct answer: answer = 1112500000
145 Correct 44 ms 52140 KB Correct answer: answer = 4294967296
146 Correct 141 ms 56308 KB Correct answer: answer = 87652406
147 Correct 143 ms 56256 KB Correct answer: answer = 6297664
148 Correct 134 ms 56260 KB Correct answer: answer = 196612
149 Correct 206 ms 60996 KB Correct answer: answer = 15015100
150 Correct 200 ms 60956 KB Correct answer: answer = 25000000
151 Correct 1798 ms 123688 KB Correct answer: answer = 333230209550
152 Correct 1748 ms 123620 KB Correct answer: answer = 917123769
153 Correct 1648 ms 123668 KB Correct answer: answer = 95162
154 Correct 202 ms 60976 KB Correct answer: answer = 382616191
155 Correct 665 ms 103716 KB Correct answer: answer = 990033333400
156 Correct 651 ms 103720 KB Correct answer: answer = 990000100000
157 Correct 1458 ms 102812 KB Correct answer: answer = 749998188180
158 Correct 538 ms 100328 KB Correct answer: answer = 1000000000000
159 Correct 1137 ms 100232 KB Correct answer: answer = 999988000036
160 Correct 1264 ms 101232 KB Correct answer: answer = 744929274393
161 Correct 1249 ms 120452 KB Correct answer: answer = 2
162 Correct 1293 ms 124744 KB Correct answer: answer = 1300024
163 Correct 1303 ms 124828 KB Correct answer: answer = 5000700010
164 Correct 1372 ms 109068 KB Correct answer: answer = 354997100800
165 Correct 161 ms 54912 KB Correct answer: answer = 257000
166 Correct 1018 ms 91988 KB Correct answer: answer = 3765323
167 Correct 454 ms 66220 KB Correct answer: answer = 1525903
168 Correct 1242 ms 114392 KB Correct answer: answer = 67618137730
169 Correct 1234 ms 113284 KB Correct answer: answer = 12656680171
170 Correct 1322 ms 114340 KB Correct answer: answer = 579831736
171 Correct 1512 ms 115408 KB Correct answer: answer = 23605611
172 Correct 1327 ms 102812 KB Correct answer: answer = 7052481200
173 Correct 1386 ms 103500 KB Correct answer: answer = 1314039500
174 Correct 1435 ms 102836 KB Correct answer: answer = 302484000
175 Correct 1606 ms 109364 KB Correct answer: answer = 52348480