oj.uz

Submission #540908

# Submission time Handle Problem Language Result Execution time Memory
540908 2022-03-21T23:46:01 Z keta_tsimakuridze Aliens (IOI16_aliens) C++14
100 / 100
 1739 ms 111780 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;
int n, m, cntL[N], cntR[N], R[N];
pii dp[N];
vector<int> 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, int x) {
	return ((ll)c.k * x + c.b);
}
ll check(ll c) {
	deque<line> dq;
	int mx = 0;
	for(ll x = 1; x <= n; x++) {
		dp[x] = {(ll)n * n + 5, 0};
		if(cntL[x - 1] + cntR[x + 1] == m) dp[x] = dp[x - 1];
		for(int j = 0; j < new_[x].size(); j++) {
			int l = new_[x][j];
			line a;
			int 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[(int)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);
	int mnl = n, mxr = 0;
    for(int i = 0; i < m; i++) {
    	if(c[i] > r1[i]) swap(c[i], r1[i]);
    	int 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, mnl); mxr = max(mxr, r1[i]);
	}
	if(k == 1) {
		return (ll)(mxr - mnl + 1) * (mxr - mnl + 1);
	}
	for(int i = 1; i <= n; i++) cntL[i] += cntL[i - 1];
	for(int i = n; i >= 1; i--) cntR[i] += cntR[i + 1];
	int C = 0;
	for(int 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 = 1e12, 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:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |   for(int 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<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 23 ms 47188 KB Correct answer: answer = 4
2 Correct 24 ms 47300 KB Correct answer: answer = 4
3 Correct 26 ms 47244 KB Correct answer: answer = 4
4 Correct 25 ms 47188 KB Correct answer: answer = 12
5 Correct 24 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47232 KB Correct answer: answer = 210
7 Correct 23 ms 47188 KB Correct answer: answer = 88
8 Correct 25 ms 47172 KB Correct answer: answer = 7696
9 Correct 22 ms 47188 KB Correct answer: answer = 1
10 Correct 23 ms 47208 KB Correct answer: answer = 2374
11 Correct 23 ms 47236 KB Correct answer: answer = 9502
12 Correct 23 ms 47172 KB Correct answer: answer = 49
13 Correct 24 ms 47268 KB Correct answer: answer = 151
14 Correct 23 ms 47212 KB Correct answer: answer = 7550
15 Correct 23 ms 47188 KB Correct answer: answer = 7220
16 Correct 23 ms 47216 KB Correct answer: answer = 7550
17 Correct 24 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47288 KB Correct answer: answer = 10000
19 Correct 23 ms 47400 KB Correct answer: answer = 624
20 Correct 23 ms 47220 KB Correct answer: answer = 10000

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 47156 KB Correct answer: answer = 1
2 Correct 24 ms 47248 KB Correct answer: answer = 4
3 Correct 23 ms 47188 KB Correct answer: answer = 1
4 Correct 23 ms 47188 KB Correct answer: answer = 5
5 Correct 23 ms 47232 KB Correct answer: answer = 41
6 Correct 24 ms 47292 KB Correct answer: answer = 71923
7 Correct 26 ms 47316 KB Correct answer: answer = 77137
8 Correct 25 ms 47344 KB Correct answer: answer = 764
9 Correct 24 ms 47316 KB Correct answer: answer = 250000
10 Correct 24 ms 47316 KB Correct answer: answer = 500
11 Correct 24 ms 47220 KB Correct answer: answer = 32
12 Correct 24 ms 47352 KB Correct answer: answer = 130050
13 Correct 24 ms 47312 KB Correct answer: answer = 5110
14 Correct 23 ms 47328 KB Correct answer: answer = 2626
15 Correct 26 ms 47208 KB Correct answer: answer = 796
16 Correct 24 ms 47356 KB Correct answer: answer = 7580
17 Correct 24 ms 47244 KB Correct answer: answer = 1904
18 Correct 22 ms 47188 KB Correct answer: answer = 996004
19 Correct 24 ms 47288 KB Correct answer: answer = 38817
20 Correct 25 ms 47340 KB Correct answer: answer = 4096
21 Correct 23 ms 47300 KB Correct answer: answer = 1
22 Correct 24 ms 47316 KB Correct answer: answer = 1
23 Correct 23 ms 47316 KB Correct answer: answer = 2040
24 Correct 23 ms 47368 KB Correct answer: answer = 2

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Correct answer: answer = 4
2 Correct 24 ms 47300 KB Correct answer: answer = 4
3 Correct 26 ms 47244 KB Correct answer: answer = 4
4 Correct 25 ms 47188 KB Correct answer: answer = 12
5 Correct 24 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47232 KB Correct answer: answer = 210
7 Correct 23 ms 47188 KB Correct answer: answer = 88
8 Correct 25 ms 47172 KB Correct answer: answer = 7696
9 Correct 22 ms 47188 KB Correct answer: answer = 1
10 Correct 23 ms 47208 KB Correct answer: answer = 2374
11 Correct 23 ms 47236 KB Correct answer: answer = 9502
12 Correct 23 ms 47172 KB Correct answer: answer = 49
13 Correct 24 ms 47268 KB Correct answer: answer = 151
14 Correct 23 ms 47212 KB Correct answer: answer = 7550
15 Correct 23 ms 47188 KB Correct answer: answer = 7220
16 Correct 23 ms 47216 KB Correct answer: answer = 7550
17 Correct 24 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47288 KB Correct answer: answer = 10000
19 Correct 23 ms 47400 KB Correct answer: answer = 624
20 Correct 23 ms 47220 KB Correct answer: answer = 10000
21 Correct 24 ms 47156 KB Correct answer: answer = 1
22 Correct 24 ms 47248 KB Correct answer: answer = 4
23 Correct 23 ms 47188 KB Correct answer: answer = 1
24 Correct 23 ms 47188 KB Correct answer: answer = 5
25 Correct 23 ms 47232 KB Correct answer: answer = 41
26 Correct 24 ms 47292 KB Correct answer: answer = 71923
27 Correct 26 ms 47316 KB Correct answer: answer = 77137
28 Correct 25 ms 47344 KB Correct answer: answer = 764
29 Correct 24 ms 47316 KB Correct answer: answer = 250000
30 Correct 24 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47220 KB Correct answer: answer = 32
32 Correct 24 ms 47352 KB Correct answer: answer = 130050
33 Correct 24 ms 47312 KB Correct answer: answer = 5110
34 Correct 23 ms 47328 KB Correct answer: answer = 2626
35 Correct 26 ms 47208 KB Correct answer: answer = 796
36 Correct 24 ms 47356 KB Correct answer: answer = 7580
37 Correct 24 ms 47244 KB Correct answer: answer = 1904
38 Correct 22 ms 47188 KB Correct answer: answer = 996004
39 Correct 24 ms 47288 KB Correct answer: answer = 38817
40 Correct 25 ms 47340 KB Correct answer: answer = 4096
41 Correct 23 ms 47300 KB Correct answer: answer = 1
42 Correct 24 ms 47316 KB Correct answer: answer = 1
43 Correct 23 ms 47316 KB Correct answer: answer = 2040
44 Correct 23 ms 47368 KB Correct answer: answer = 2
45 Correct 22 ms 47244 KB Correct answer: answer = 4
46 Correct 22 ms 47260 KB Correct answer: answer = 9
47 Correct 23 ms 47248 KB Correct answer: answer = 9
48 Correct 23 ms 47188 KB Correct answer: answer = 21
49 Correct 23 ms 47188 KB Correct answer: answer = 71
50 Correct 23 ms 47184 KB Correct answer: answer = 77
51 Correct 24 ms 47188 KB Correct answer: answer = 400
52 Correct 24 ms 47320 KB Correct answer: answer = 996004
53 Correct 23 ms 47348 KB Correct answer: answer = 997310
54 Correct 25 ms 47348 KB Correct answer: answer = 990781
55 Correct 25 ms 47316 KB Correct answer: answer = 996545
56 Correct 24 ms 47308 KB Correct answer: answer = 484
57 Correct 23 ms 47308 KB Correct answer: answer = 484
58 Correct 23 ms 47308 KB Correct answer: answer = 63501
59 Correct 24 ms 47272 KB Correct answer: answer = 323501
60 Correct 25 ms 47328 KB Correct answer: answer = 752500
61 Correct 25 ms 47268 KB Correct answer: answer = 761480
62 Correct 24 ms 47348 KB Correct answer: answer = 758932
63 Correct 24 ms 47196 KB Correct answer: answer = 1000000
64 Correct 24 ms 47324 KB Correct answer: answer = 750500
65 Correct 24 ms 47272 KB Correct answer: answer = 1000000
66 Correct 23 ms 47188 KB Correct answer: answer = 250000
67 Correct 24 ms 47188 KB Correct answer: answer = 250000
68 Correct 24 ms 47316 KB Correct answer: answer = 1000000
69 Correct 24 ms 47280 KB Correct answer: answer = 994009
70 Correct 25 ms 47316 KB Correct answer: answer = 59315
71 Correct 25 ms 47300 KB Correct answer: answer = 25454
72 Correct 25 ms 47316 KB Correct answer: answer = 1504
73 Correct 24 ms 47316 KB Correct answer: answer = 37486
74 Correct 25 ms 47316 KB Correct answer: answer = 4284
75 Correct 24 ms 47232 KB Correct answer: answer = 158008
76 Correct 25 ms 47352 KB Correct answer: answer = 51860
77 Correct 24 ms 47316 KB Correct answer: answer = 12985
78 Correct 1122 ms 78912 KB Correct answer: answer = 997864126212
79 Correct 1039 ms 78936 KB Correct answer: answer = 998608411647
80 Correct 1106 ms 79096 KB Correct answer: answer = 995265560477
81 Correct 31 ms 47692 KB Correct answer: answer = 10125000
82 Correct 30 ms 47784 KB Correct answer: answer = 2291668
83 Correct 26 ms 47436 KB Correct answer: answer = 42388
84 Correct 26 ms 47456 KB Correct answer: answer = 10318
85 Correct 27 ms 47384 KB Correct answer: answer = 3416
86 Correct 1712 ms 106172 KB Correct answer: answer = 331708193881
87 Correct 1467 ms 106148 KB Correct answer: answer = 2861193756
88 Correct 1391 ms 106144 KB Correct answer: answer = 114646930
89 Correct 32 ms 47700 KB Correct answer: answer = 9280921
90 Correct 472 ms 78880 KB Correct answer: answer = 999984053400
91 Correct 1195 ms 79672 KB Correct answer: answer = 750935949134
92 Correct 455 ms 78840 KB Correct answer: answer = 1000000000000
93 Correct 1069 ms 78768 KB Correct answer: answer = 998762383161
94 Correct 1590 ms 104632 KB Correct answer: answer = 23017412908
95 Correct 1093 ms 79348 KB Correct answer: answer = 728143410622
96 Correct 1217 ms 106060 KB Correct answer: answer = 2
97 Correct 1194 ms 106344 KB Correct answer: answer = 1824916
98 Correct 173 ms 53452 KB Correct answer: answer = 10680029
99 Correct 165 ms 53344 KB Correct answer: answer = 18351700
100 Correct 1300 ms 106148 KB Correct answer: answer = 16040026
101 Correct 1115 ms 92228 KB Correct answer: answer = 253968628325
102 Correct 28 ms 47444 KB Correct answer: answer = 10267
103 Correct 734 ms 77204 KB Correct answer: answer = 2582408
104 Correct 1134 ms 95824 KB Correct answer: answer = 78024964781
105 Correct 1198 ms 99104 KB Correct answer: answer = 9866346457
106 Correct 1211 ms 93436 KB Correct answer: answer = 3327720949
107 Correct 1116 ms 80200 KB Correct answer: answer = 86064128360
108 Correct 1155 ms 81100 KB Correct answer: answer = 12698259150
109 Correct 1271 ms 84208 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Correct answer: answer = 4
2 Correct 24 ms 47300 KB Correct answer: answer = 4
3 Correct 26 ms 47244 KB Correct answer: answer = 4
4 Correct 25 ms 47188 KB Correct answer: answer = 12
5 Correct 24 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47232 KB Correct answer: answer = 210
7 Correct 23 ms 47188 KB Correct answer: answer = 88
8 Correct 25 ms 47172 KB Correct answer: answer = 7696
9 Correct 22 ms 47188 KB Correct answer: answer = 1
10 Correct 23 ms 47208 KB Correct answer: answer = 2374
11 Correct 23 ms 47236 KB Correct answer: answer = 9502
12 Correct 23 ms 47172 KB Correct answer: answer = 49
13 Correct 24 ms 47268 KB Correct answer: answer = 151
14 Correct 23 ms 47212 KB Correct answer: answer = 7550
15 Correct 23 ms 47188 KB Correct answer: answer = 7220
16 Correct 23 ms 47216 KB Correct answer: answer = 7550
17 Correct 24 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47288 KB Correct answer: answer = 10000
19 Correct 23 ms 47400 KB Correct answer: answer = 624
20 Correct 23 ms 47220 KB Correct answer: answer = 10000
21 Correct 24 ms 47156 KB Correct answer: answer = 1
22 Correct 24 ms 47248 KB Correct answer: answer = 4
23 Correct 23 ms 47188 KB Correct answer: answer = 1
24 Correct 23 ms 47188 KB Correct answer: answer = 5
25 Correct 23 ms 47232 KB Correct answer: answer = 41
26 Correct 24 ms 47292 KB Correct answer: answer = 71923
27 Correct 26 ms 47316 KB Correct answer: answer = 77137
28 Correct 25 ms 47344 KB Correct answer: answer = 764
29 Correct 24 ms 47316 KB Correct answer: answer = 250000
30 Correct 24 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47220 KB Correct answer: answer = 32
32 Correct 24 ms 47352 KB Correct answer: answer = 130050
33 Correct 24 ms 47312 KB Correct answer: answer = 5110
34 Correct 23 ms 47328 KB Correct answer: answer = 2626
35 Correct 26 ms 47208 KB Correct answer: answer = 796
36 Correct 24 ms 47356 KB Correct answer: answer = 7580
37 Correct 24 ms 47244 KB Correct answer: answer = 1904
38 Correct 22 ms 47188 KB Correct answer: answer = 996004
39 Correct 24 ms 47288 KB Correct answer: answer = 38817
40 Correct 25 ms 47340 KB Correct answer: answer = 4096
41 Correct 23 ms 47300 KB Correct answer: answer = 1
42 Correct 24 ms 47316 KB Correct answer: answer = 1
43 Correct 23 ms 47316 KB Correct answer: answer = 2040
44 Correct 23 ms 47368 KB Correct answer: answer = 2
45 Correct 22 ms 47244 KB Correct answer: answer = 4
46 Correct 22 ms 47260 KB Correct answer: answer = 9
47 Correct 23 ms 47248 KB Correct answer: answer = 9
48 Correct 23 ms 47188 KB Correct answer: answer = 21
49 Correct 23 ms 47188 KB Correct answer: answer = 71
50 Correct 23 ms 47184 KB Correct answer: answer = 77
51 Correct 24 ms 47188 KB Correct answer: answer = 400
52 Correct 24 ms 47320 KB Correct answer: answer = 996004
53 Correct 23 ms 47348 KB Correct answer: answer = 997310
54 Correct 25 ms 47348 KB Correct answer: answer = 990781
55 Correct 25 ms 47316 KB Correct answer: answer = 996545
56 Correct 24 ms 47308 KB Correct answer: answer = 484
57 Correct 23 ms 47308 KB Correct answer: answer = 484
58 Correct 23 ms 47308 KB Correct answer: answer = 63501
59 Correct 24 ms 47272 KB Correct answer: answer = 323501
60 Correct 25 ms 47328 KB Correct answer: answer = 752500
61 Correct 25 ms 47268 KB Correct answer: answer = 761480
62 Correct 24 ms 47348 KB Correct answer: answer = 758932
63 Correct 24 ms 47196 KB Correct answer: answer = 1000000
64 Correct 24 ms 47324 KB Correct answer: answer = 750500
65 Correct 24 ms 47272 KB Correct answer: answer = 1000000
66 Correct 23 ms 47188 KB Correct answer: answer = 250000
67 Correct 24 ms 47188 KB Correct answer: answer = 250000
68 Correct 24 ms 47316 KB Correct answer: answer = 1000000
69 Correct 24 ms 47280 KB Correct answer: answer = 994009
70 Correct 25 ms 47316 KB Correct answer: answer = 59315
71 Correct 25 ms 47300 KB Correct answer: answer = 25454
72 Correct 25 ms 47316 KB Correct answer: answer = 1504
73 Correct 24 ms 47316 KB Correct answer: answer = 37486
74 Correct 25 ms 47316 KB Correct answer: answer = 4284
75 Correct 24 ms 47232 KB Correct answer: answer = 158008
76 Correct 25 ms 47352 KB Correct answer: answer = 51860
77 Correct 24 ms 47316 KB Correct answer: answer = 12985
78 Correct 1122 ms 78912 KB Correct answer: answer = 997864126212
79 Correct 1039 ms 78936 KB Correct answer: answer = 998608411647
80 Correct 1106 ms 79096 KB Correct answer: answer = 995265560477
81 Correct 31 ms 47692 KB Correct answer: answer = 10125000
82 Correct 30 ms 47784 KB Correct answer: answer = 2291668
83 Correct 26 ms 47436 KB Correct answer: answer = 42388
84 Correct 26 ms 47456 KB Correct answer: answer = 10318
85 Correct 27 ms 47384 KB Correct answer: answer = 3416
86 Correct 1712 ms 106172 KB Correct answer: answer = 331708193881
87 Correct 1467 ms 106148 KB Correct answer: answer = 2861193756
88 Correct 1391 ms 106144 KB Correct answer: answer = 114646930
89 Correct 32 ms 47700 KB Correct answer: answer = 9280921
90 Correct 472 ms 78880 KB Correct answer: answer = 999984053400
91 Correct 1195 ms 79672 KB Correct answer: answer = 750935949134
92 Correct 455 ms 78840 KB Correct answer: answer = 1000000000000
93 Correct 1069 ms 78768 KB Correct answer: answer = 998762383161
94 Correct 1590 ms 104632 KB Correct answer: answer = 23017412908
95 Correct 1093 ms 79348 KB Correct answer: answer = 728143410622
96 Correct 1217 ms 106060 KB Correct answer: answer = 2
97 Correct 1194 ms 106344 KB Correct answer: answer = 1824916
98 Correct 173 ms 53452 KB Correct answer: answer = 10680029
99 Correct 165 ms 53344 KB Correct answer: answer = 18351700
100 Correct 1300 ms 106148 KB Correct answer: answer = 16040026
101 Correct 1115 ms 92228 KB Correct answer: answer = 253968628325
102 Correct 28 ms 47444 KB Correct answer: answer = 10267
103 Correct 734 ms 77204 KB Correct answer: answer = 2582408
104 Correct 1134 ms 95824 KB Correct answer: answer = 78024964781
105 Correct 1198 ms 99104 KB Correct answer: answer = 9866346457
106 Correct 1211 ms 93436 KB Correct answer: answer = 3327720949
107 Correct 1116 ms 80200 KB Correct answer: answer = 86064128360
108 Correct 1155 ms 81100 KB Correct answer: answer = 12698259150
109 Correct 1271 ms 84208 KB Correct answer: answer = 1185259288
110 Correct 607 ms 81328 KB Correct answer: answer = 999889968863
111 Correct 1070 ms 82944 KB Correct answer: answer = 999861384931
112 Correct 1046 ms 82620 KB Correct answer: answer = 999811809929
113 Correct 526 ms 81052 KB Correct answer: answer = 999869756441
114 Correct 134 ms 53684 KB Correct answer: answer = 1700000000
115 Correct 123 ms 53580 KB Correct answer: answer = 131666670
116 Correct 50 ms 49108 KB Correct answer: answer = 89478486
117 Correct 56 ms 49152 KB Correct answer: answer = 4971040
118 Correct 52 ms 49108 KB Correct answer: answer = 2711494
119 Correct 110 ms 52892 KB Correct answer: answer = 25252530
120 Correct 103 ms 52940 KB Correct answer: answer = 62500000
121 Correct 1622 ms 108280 KB Correct answer: answer = 333175097780
122 Correct 1722 ms 108284 KB Correct answer: answer = 33121180179
123 Correct 1642 ms 108280 KB Correct answer: answer = 9802314015
124 Correct 107 ms 52980 KB Correct answer: answer = 32567551
125 Correct 525 ms 82972 KB Correct answer: answer = 997525000000
126 Correct 1408 ms 82576 KB Correct answer: answer = 752723538884
127 Correct 466 ms 81076 KB Correct answer: answer = 1000000000000
128 Correct 1073 ms 80984 KB Correct answer: answer = 999978000121
129 Correct 1194 ms 81520 KB Correct answer: answer = 745986144735
130 Correct 1232 ms 107004 KB Correct answer: answer = 2
131 Correct 1237 ms 108884 KB Correct answer: answer = 277966670
132 Correct 1228 ms 108324 KB Correct answer: answer = 2500900082
133 Correct 1227 ms 92940 KB Correct answer: answer = 301248349636
134 Correct 95 ms 50392 KB Correct answer: answer = 14118891
135 Correct 1230 ms 103356 KB Correct answer: answer = 14384977265
136 Correct 1232 ms 99248 KB Correct answer: answer = 3681368330
137 Correct 1340 ms 97484 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47188 KB Correct answer: answer = 4
2 Correct 24 ms 47300 KB Correct answer: answer = 4
3 Correct 26 ms 47244 KB Correct answer: answer = 4
4 Correct 25 ms 47188 KB Correct answer: answer = 12
5 Correct 24 ms 47188 KB Correct answer: answer = 52
6 Correct 23 ms 47232 KB Correct answer: answer = 210
7 Correct 23 ms 47188 KB Correct answer: answer = 88
8 Correct 25 ms 47172 KB Correct answer: answer = 7696
9 Correct 22 ms 47188 KB Correct answer: answer = 1
10 Correct 23 ms 47208 KB Correct answer: answer = 2374
11 Correct 23 ms 47236 KB Correct answer: answer = 9502
12 Correct 23 ms 47172 KB Correct answer: answer = 49
13 Correct 24 ms 47268 KB Correct answer: answer = 151
14 Correct 23 ms 47212 KB Correct answer: answer = 7550
15 Correct 23 ms 47188 KB Correct answer: answer = 7220
16 Correct 23 ms 47216 KB Correct answer: answer = 7550
17 Correct 24 ms 47188 KB Correct answer: answer = 10000
18 Correct 23 ms 47288 KB Correct answer: answer = 10000
19 Correct 23 ms 47400 KB Correct answer: answer = 624
20 Correct 23 ms 47220 KB Correct answer: answer = 10000
21 Correct 24 ms 47156 KB Correct answer: answer = 1
22 Correct 24 ms 47248 KB Correct answer: answer = 4
23 Correct 23 ms 47188 KB Correct answer: answer = 1
24 Correct 23 ms 47188 KB Correct answer: answer = 5
25 Correct 23 ms 47232 KB Correct answer: answer = 41
26 Correct 24 ms 47292 KB Correct answer: answer = 71923
27 Correct 26 ms 47316 KB Correct answer: answer = 77137
28 Correct 25 ms 47344 KB Correct answer: answer = 764
29 Correct 24 ms 47316 KB Correct answer: answer = 250000
30 Correct 24 ms 47316 KB Correct answer: answer = 500
31 Correct 24 ms 47220 KB Correct answer: answer = 32
32 Correct 24 ms 47352 KB Correct answer: answer = 130050
33 Correct 24 ms 47312 KB Correct answer: answer = 5110
34 Correct 23 ms 47328 KB Correct answer: answer = 2626
35 Correct 26 ms 47208 KB Correct answer: answer = 796
36 Correct 24 ms 47356 KB Correct answer: answer = 7580
37 Correct 24 ms 47244 KB Correct answer: answer = 1904
38 Correct 22 ms 47188 KB Correct answer: answer = 996004
39 Correct 24 ms 47288 KB Correct answer: answer = 38817
40 Correct 25 ms 47340 KB Correct answer: answer = 4096
41 Correct 23 ms 47300 KB Correct answer: answer = 1
42 Correct 24 ms 47316 KB Correct answer: answer = 1
43 Correct 23 ms 47316 KB Correct answer: answer = 2040
44 Correct 23 ms 47368 KB Correct answer: answer = 2
45 Correct 22 ms 47244 KB Correct answer: answer = 4
46 Correct 22 ms 47260 KB Correct answer: answer = 9
47 Correct 23 ms 47248 KB Correct answer: answer = 9
48 Correct 23 ms 47188 KB Correct answer: answer = 21
49 Correct 23 ms 47188 KB Correct answer: answer = 71
50 Correct 23 ms 47184 KB Correct answer: answer = 77
51 Correct 24 ms 47188 KB Correct answer: answer = 400
52 Correct 24 ms 47320 KB Correct answer: answer = 996004
53 Correct 23 ms 47348 KB Correct answer: answer = 997310
54 Correct 25 ms 47348 KB Correct answer: answer = 990781
55 Correct 25 ms 47316 KB Correct answer: answer = 996545
56 Correct 24 ms 47308 KB Correct answer: answer = 484
57 Correct 23 ms 47308 KB Correct answer: answer = 484
58 Correct 23 ms 47308 KB Correct answer: answer = 63501
59 Correct 24 ms 47272 KB Correct answer: answer = 323501
60 Correct 25 ms 47328 KB Correct answer: answer = 752500
61 Correct 25 ms 47268 KB Correct answer: answer = 761480
62 Correct 24 ms 47348 KB Correct answer: answer = 758932
63 Correct 24 ms 47196 KB Correct answer: answer = 1000000
64 Correct 24 ms 47324 KB Correct answer: answer = 750500
65 Correct 24 ms 47272 KB Correct answer: answer = 1000000
66 Correct 23 ms 47188 KB Correct answer: answer = 250000
67 Correct 24 ms 47188 KB Correct answer: answer = 250000
68 Correct 24 ms 47316 KB Correct answer: answer = 1000000
69 Correct 24 ms 47280 KB Correct answer: answer = 994009
70 Correct 25 ms 47316 KB Correct answer: answer = 59315
71 Correct 25 ms 47300 KB Correct answer: answer = 25454
72 Correct 25 ms 47316 KB Correct answer: answer = 1504
73 Correct 24 ms 47316 KB Correct answer: answer = 37486
74 Correct 25 ms 47316 KB Correct answer: answer = 4284
75 Correct 24 ms 47232 KB Correct answer: answer = 158008
76 Correct 25 ms 47352 KB Correct answer: answer = 51860
77 Correct 24 ms 47316 KB Correct answer: answer = 12985
78 Correct 1122 ms 78912 KB Correct answer: answer = 997864126212
79 Correct 1039 ms 78936 KB Correct answer: answer = 998608411647
80 Correct 1106 ms 79096 KB Correct answer: answer = 995265560477
81 Correct 31 ms 47692 KB Correct answer: answer = 10125000
82 Correct 30 ms 47784 KB Correct answer: answer = 2291668
83 Correct 26 ms 47436 KB Correct answer: answer = 42388
84 Correct 26 ms 47456 KB Correct answer: answer = 10318
85 Correct 27 ms 47384 KB Correct answer: answer = 3416
86 Correct 1712 ms 106172 KB Correct answer: answer = 331708193881
87 Correct 1467 ms 106148 KB Correct answer: answer = 2861193756
88 Correct 1391 ms 106144 KB Correct answer: answer = 114646930
89 Correct 32 ms 47700 KB Correct answer: answer = 9280921
90 Correct 472 ms 78880 KB Correct answer: answer = 999984053400
91 Correct 1195 ms 79672 KB Correct answer: answer = 750935949134
92 Correct 455 ms 78840 KB Correct answer: answer = 1000000000000
93 Correct 1069 ms 78768 KB Correct answer: answer = 998762383161
94 Correct 1590 ms 104632 KB Correct answer: answer = 23017412908
95 Correct 1093 ms 79348 KB Correct answer: answer = 728143410622
96 Correct 1217 ms 106060 KB Correct answer: answer = 2
97 Correct 1194 ms 106344 KB Correct answer: answer = 1824916
98 Correct 173 ms 53452 KB Correct answer: answer = 10680029
99 Correct 165 ms 53344 KB Correct answer: answer = 18351700
100 Correct 1300 ms 106148 KB Correct answer: answer = 16040026
101 Correct 1115 ms 92228 KB Correct answer: answer = 253968628325
102 Correct 28 ms 47444 KB Correct answer: answer = 10267
103 Correct 734 ms 77204 KB Correct answer: answer = 2582408
104 Correct 1134 ms 95824 KB Correct answer: answer = 78024964781
105 Correct 1198 ms 99104 KB Correct answer: answer = 9866346457
106 Correct 1211 ms 93436 KB Correct answer: answer = 3327720949
107 Correct 1116 ms 80200 KB Correct answer: answer = 86064128360
108 Correct 1155 ms 81100 KB Correct answer: answer = 12698259150
109 Correct 1271 ms 84208 KB Correct answer: answer = 1185259288
110 Correct 607 ms 81328 KB Correct answer: answer = 999889968863
111 Correct 1070 ms 82944 KB Correct answer: answer = 999861384931
112 Correct 1046 ms 82620 KB Correct answer: answer = 999811809929
113 Correct 526 ms 81052 KB Correct answer: answer = 999869756441
114 Correct 134 ms 53684 KB Correct answer: answer = 1700000000
115 Correct 123 ms 53580 KB Correct answer: answer = 131666670
116 Correct 50 ms 49108 KB Correct answer: answer = 89478486
117 Correct 56 ms 49152 KB Correct answer: answer = 4971040
118 Correct 52 ms 49108 KB Correct answer: answer = 2711494
119 Correct 110 ms 52892 KB Correct answer: answer = 25252530
120 Correct 103 ms 52940 KB Correct answer: answer = 62500000
121 Correct 1622 ms 108280 KB Correct answer: answer = 333175097780
122 Correct 1722 ms 108284 KB Correct answer: answer = 33121180179
123 Correct 1642 ms 108280 KB Correct answer: answer = 9802314015
124 Correct 107 ms 52980 KB Correct answer: answer = 32567551
125 Correct 525 ms 82972 KB Correct answer: answer = 997525000000
126 Correct 1408 ms 82576 KB Correct answer: answer = 752723538884
127 Correct 466 ms 81076 KB Correct answer: answer = 1000000000000
128 Correct 1073 ms 80984 KB Correct answer: answer = 999978000121
129 Correct 1194 ms 81520 KB Correct answer: answer = 745986144735
130 Correct 1232 ms 107004 KB Correct answer: answer = 2
131 Correct 1237 ms 108884 KB Correct answer: answer = 277966670
132 Correct 1228 ms 108324 KB Correct answer: answer = 2500900082
133 Correct 1227 ms 92940 KB Correct answer: answer = 301248349636
134 Correct 95 ms 50392 KB Correct answer: answer = 14118891
135 Correct 1230 ms 103356 KB Correct answer: answer = 14384977265
136 Correct 1232 ms 99248 KB Correct answer: answer = 3681368330
137 Correct 1340 ms 97484 KB Correct answer: answer = 2720316816
138 Correct 68 ms 59476 KB Correct answer: answer = 999976000144
139 Correct 1178 ms 83240 KB Correct answer: answer = 999856102410
140 Correct 1127 ms 83212 KB Correct answer: answer = 999958401531
141 Correct 1230 ms 83256 KB Correct answer: answer = 999769649944
142 Correct 1187 ms 85148 KB Correct answer: answer = 999874525918
143 Correct 216 ms 59452 KB Correct answer: answer = 6050000000
144 Correct 252 ms 59508 KB Correct answer: answer = 1112500000
145 Correct 40 ms 50876 KB Correct answer: answer = 4294967296
146 Correct 140 ms 54732 KB Correct answer: answer = 87652406
147 Correct 133 ms 54704 KB Correct answer: answer = 6297664
148 Correct 130 ms 54728 KB Correct answer: answer = 196612
149 Correct 194 ms 58676 KB Correct answer: answer = 15015100
150 Correct 198 ms 58676 KB Correct answer: answer = 25000000
151 Correct 1739 ms 110516 KB Correct answer: answer = 333230209550
152 Correct 1702 ms 110520 KB Correct answer: answer = 917123769
153 Correct 1562 ms 110524 KB Correct answer: answer = 95162
154 Correct 201 ms 58636 KB Correct answer: answer = 382616191
155 Correct 593 ms 87100 KB Correct answer: answer = 990033333400
156 Correct 589 ms 87092 KB Correct answer: answer = 990000100000
157 Correct 1394 ms 85352 KB Correct answer: answer = 749998188180
158 Correct 470 ms 83404 KB Correct answer: answer = 1000000000000
159 Correct 1059 ms 83088 KB Correct answer: answer = 999988000036
160 Correct 1165 ms 83884 KB Correct answer: answer = 744929274393
161 Correct 1151 ms 108052 KB Correct answer: answer = 2
162 Correct 1205 ms 111760 KB Correct answer: answer = 1300024
163 Correct 1221 ms 111780 KB Correct answer: answer = 5000700010
164 Correct 1282 ms 93408 KB Correct answer: answer = 354997100800
165 Correct 160 ms 53476 KB Correct answer: answer = 257000
166 Correct 972 ms 83872 KB Correct answer: answer = 3765323
167 Correct 433 ms 62628 KB Correct answer: answer = 1525903
168 Correct 1174 ms 99608 KB Correct answer: answer = 67618137730
169 Correct 1202 ms 98340 KB Correct answer: answer = 12656680171
170 Correct 1287 ms 98888 KB Correct answer: answer = 579831736
171 Correct 1461 ms 100080 KB Correct answer: answer = 23605611
172 Correct 1226 ms 84948 KB Correct answer: answer = 7052481200
173 Correct 1320 ms 85684 KB Correct answer: answer = 1314039500
174 Correct 1357 ms 85736 KB Correct answer: answer = 302484000
175 Correct 1549 ms 92572 KB Correct answer: answer = 52348480