oj.uz

Submission #799063

# Submission time Handle Problem Language Result Execution time Memory
799063 2023-07-31T09:10:36 Z NothingXD Aliens (IOI16_aliens) C++17
100 / 100
 162 ms 14108 KB 
#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out() {cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e5 + 10;

int n, m, k; 
pll dp[maxn];
ll x[maxn], y[maxn], z[maxn];
vector<pll> p;

struct CHT{
	static const ll inf = 1e18;
	int l, r;
	vector<pll> a;
	CHT(int _n){
		a.resize(_n);
		l = r = 0;
	}
	ll insec(int l1, int l2){
		assert(x[l1] != x[l2]);
		if (x[l1] > x[l2]) swap(l1, l2);
		return (y[l1] - y[l2] + (y[l1] <= y[l2]? 0: 1) * (x[l2] - x[l1] - 1)) / (x[l2] - x[l1]);
	}
	void add(int idx){
		ll tmp;
		while(r){
			tmp = insec(a[r-1].S, idx);
			//debug(tmp);
			if (x[a[r-1].S] * tmp + y[a[r-1].S] == x[idx] * tmp + y[idx] && z[a[r-1].S] < z[idx]) tmp++;
			if (tmp <= a[r-1].F) r--;
			else break;
		}
		if (!r) a[r++] = {-inf, idx};
		else a[r] = {tmp, idx}, r++;
		//debug(r-1, a[r-1].F, a[r-1].S);
	}
	pll get(ll tmp){
		while(l + 1 < r && a[l+1].F <= tmp) l++;
		return MP(x[a[l].S] * tmp + y[a[l].S], z[a[l].S]);
	}
};

pll Calc(ll lan){
	//debug(lan);
	CHT cht(n);
	dp[0] = {(p[0].S - p[0].F) * (p[0].S - p[0].F) + lan, 1};
	x[0] = -p[0].F;
	y[0] = p[0].F * p[0].F;
	z[0] = 0;
	//debug(x[0], y[0], z[0]);
	//debug(dp[0].F, dp[0].S);
	cht.add(0);
	for (int i = 1; i < n; i++){
		/*dp[i] = {(p[i].S-p[0].F) * (p[i].S-p[0].F) + lan, 1};
		for (int j = 1; j <= i; j++){
			dp[i] = min(dp[i], MP(dp[j-1].F + (p[i].S-p[j].F)*(p[i].S-p[j].F) - (p[j-1].S > p[j].F? (p[j-1].S-p[j].F) * (p[j-1].S-p[j].F): 0) + lan, dp[j-1].S + 1));
		}*/
		x[i] = -p[i].F;
		y[i] = dp[i-1].F + p[i].F * p[i].F - (p[i-1].S > p[i].F? (p[i-1].S-p[i].F)*(p[i-1].S-p[i].F): 0);
		z[i] = dp[i-1].S;
		//debug(x[i], y[i], z[i]);
		cht.add(i);
		pll val = cht.get(2*p[i].S);
		dp[i] = {val.F + (p[i].S) * (p[i].S) + lan, val.S+1};
		//debug(i, dp[i].F, dp[i].S);
	}
	return dp[n-1];
}

const int maxa = 1e6 + 10;
int mx[maxa];

long long take_photos(int _n, int _m, int _k, std::vector<int> R, std::vector<int> C) {
	/*CHT cht(n);
	x[0] = ;
	y[0] = 2;
	x[1] = 10;
	y[1] = 15;
	return cht.insec(0, 1);*/
	memset(mx, -1, sizeof mx);
	n = _n, m = _m, k = _k;
	for (int i = 0; i < n; i++){
		if (R[i] > C[i]) swap(R[i], C[i]);
		mx[R[i]] = max(mx[R[i]], C[i]);
	}
	for (int i = 0; i < m; i++){
		if (mx[i] == -1) continue;
		if (p.empty() || (p.back().S) < mx[i]) p.push_back({i, mx[i]});
	}
	k = min(k, (int)p.size());
	n = p.size();
	for (int i = 0; i < n; i++){
		//debug(i, p[i].F, p[i].S);
		p[i].S++;
	}
	ll l = -1, r = 1e12;
	while(l + 1 < r){
		//debug(l, r);
		ll mid = (l + r) >> 1;
		pll tmp = Calc(mid);
		if (tmp.S <= k) r = mid;
		else l = mid;
	}
	//debug(r);
	pll tmp = Calc(r);
	return tmp.F - r * k;
}

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Correct answer: answer = 4
2 Correct 2 ms 4180 KB Correct answer: answer = 4
3 Correct 2 ms 4180 KB Correct answer: answer = 4
4 Correct 2 ms 4180 KB Correct answer: answer = 12
5 Correct 2 ms 4180 KB Correct answer: answer = 52
6 Correct 2 ms 4180 KB Correct answer: answer = 210
7 Correct 2 ms 4180 KB Correct answer: answer = 88
8 Correct 2 ms 4180 KB Correct answer: answer = 7696
9 Correct 2 ms 4180 KB Correct answer: answer = 1
10 Correct 2 ms 4180 KB Correct answer: answer = 2374
11 Correct 2 ms 4180 KB Correct answer: answer = 9502
12 Correct 2 ms 4176 KB Correct answer: answer = 49
13 Correct 2 ms 4180 KB Correct answer: answer = 151
14 Correct 2 ms 4180 KB Correct answer: answer = 7550
15 Correct 2 ms 4180 KB Correct answer: answer = 7220
16 Correct 2 ms 4180 KB Correct answer: answer = 7550
17 Correct 2 ms 4180 KB Correct answer: answer = 10000
18 Correct 2 ms 4232 KB Correct answer: answer = 10000
19 Correct 2 ms 4220 KB Correct answer: answer = 624
20 Correct 2 ms 4180 KB Correct answer: answer = 10000
21 Correct 2 ms 4180 KB Correct answer: answer = 1
22 Correct 2 ms 4180 KB Correct answer: answer = 4
23 Correct 2 ms 4180 KB Correct answer: answer = 1
24 Correct 2 ms 4180 KB Correct answer: answer = 5
25 Correct 2 ms 4180 KB Correct answer: answer = 41
26 Correct 2 ms 4180 KB Correct answer: answer = 71923
27 Correct 2 ms 4180 KB Correct answer: answer = 77137
28 Correct 2 ms 4180 KB Correct answer: answer = 764
29 Correct 2 ms 4272 KB Correct answer: answer = 250000
30 Correct 3 ms 4180 KB Correct answer: answer = 500
31 Correct 2 ms 4180 KB Correct answer: answer = 32
32 Correct 2 ms 4180 KB Correct answer: answer = 130050
33 Correct 2 ms 4180 KB Correct answer: answer = 5110
34 Correct 2 ms 4180 KB Correct answer: answer = 2626
35 Correct 2 ms 4180 KB Correct answer: answer = 796
36 Correct 2 ms 4180 KB Correct answer: answer = 7580
37 Correct 3 ms 4180 KB Correct answer: answer = 1904
38 Correct 2 ms 4180 KB Correct answer: answer = 996004
39 Correct 2 ms 4180 KB Correct answer: answer = 38817
40 Correct 2 ms 4180 KB Correct answer: answer = 4096
41 Correct 2 ms 4180 KB Correct answer: answer = 1
42 Correct 2 ms 4180 KB Correct answer: answer = 1
43 Correct 2 ms 4180 KB Correct answer: answer = 2040
44 Correct 2 ms 4180 KB Correct answer: answer = 2
45 Correct 2 ms 4180 KB Correct answer: answer = 4
46 Correct 2 ms 4236 KB Correct answer: answer = 9
47 Correct 2 ms 4180 KB Correct answer: answer = 9
48 Correct 2 ms 4176 KB Correct answer: answer = 21
49 Correct 2 ms 4180 KB Correct answer: answer = 71
50 Correct 2 ms 4180 KB Correct answer: answer = 77
51 Correct 2 ms 4180 KB Correct answer: answer = 400
52 Correct 3 ms 4180 KB Correct answer: answer = 996004
53 Correct 2 ms 4180 KB Correct answer: answer = 997310
54 Correct 2 ms 4180 KB Correct answer: answer = 990781
55 Correct 2 ms 4180 KB Correct answer: answer = 996545
56 Correct 2 ms 4180 KB Correct answer: answer = 484
57 Correct 2 ms 4180 KB Correct answer: answer = 484
58 Correct 2 ms 4180 KB Correct answer: answer = 63501
59 Correct 2 ms 4180 KB Correct answer: answer = 323501
60 Correct 2 ms 4180 KB Correct answer: answer = 752500
61 Correct 2 ms 4180 KB Correct answer: answer = 761480
62 Correct 2 ms 4180 KB Correct answer: answer = 758932
63 Correct 2 ms 4180 KB Correct answer: answer = 1000000
64 Correct 2 ms 4180 KB Correct answer: answer = 750500
65 Correct 2 ms 4240 KB Correct answer: answer = 1000000
66 Correct 2 ms 4180 KB Correct answer: answer = 250000
67 Correct 2 ms 4180 KB Correct answer: answer = 250000
68 Correct 2 ms 4180 KB Correct answer: answer = 1000000
69 Correct 2 ms 4180 KB Correct answer: answer = 994009
70 Correct 2 ms 4180 KB Correct answer: answer = 59315
71 Correct 2 ms 4180 KB Correct answer: answer = 25454
72 Correct 2 ms 4180 KB Correct answer: answer = 1504
73 Correct 2 ms 4180 KB Correct answer: answer = 37486
74 Correct 2 ms 4180 KB Correct answer: answer = 4284
75 Correct 2 ms 4180 KB Correct answer: answer = 158008
76 Correct 2 ms 4180 KB Correct answer: answer = 51860
77 Correct 2 ms 4180 KB Correct answer: answer = 12985
78 Correct 3 ms 4180 KB Correct answer: answer = 997864126212
79 Correct 3 ms 4180 KB Correct answer: answer = 998608411647
80 Correct 3 ms 4180 KB Correct answer: answer = 995265560477
81 Correct 5 ms 4576 KB Correct answer: answer = 10125000
82 Correct 5 ms 4572 KB Correct answer: answer = 2291668
83 Correct 3 ms 4448 KB Correct answer: answer = 42388
84 Correct 5 ms 4436 KB Correct answer: answer = 10318
85 Correct 4 ms 4436 KB Correct answer: answer = 3416
86 Correct 9 ms 4692 KB Correct answer: answer = 331708193881
87 Correct 7 ms 4708 KB Correct answer: answer = 2861193756
88 Correct 10 ms 4684 KB Correct answer: answer = 114646930
89 Correct 5 ms 4612 KB Correct answer: answer = 9280921
90 Correct 6 ms 4684 KB Correct answer: answer = 999984053400
91 Correct 8 ms 4572 KB Correct answer: answer = 750935949134
92 Correct 5 ms 4232 KB Correct answer: answer = 1000000000000
93 Correct 3 ms 4288 KB Correct answer: answer = 998762383161
94 Correct 7 ms 4568 KB Correct answer: answer = 23017412908
95 Correct 8 ms 4312 KB Correct answer: answer = 728143410622
96 Correct 4 ms 4308 KB Correct answer: answer = 2
97 Correct 6 ms 4556 KB Correct answer: answer = 1824916
98 Correct 7 ms 4628 KB Correct answer: answer = 10680029
99 Correct 7 ms 4620 KB Correct answer: answer = 18351700
100 Correct 6 ms 4576 KB Correct answer: answer = 16040026
101 Correct 4 ms 4300 KB Correct answer: answer = 253968628325
102 Correct 4 ms 4576 KB Correct answer: answer = 10267
103 Correct 6 ms 4692 KB Correct answer: answer = 2582408
104 Correct 7 ms 4296 KB Correct answer: answer = 78024964781
105 Correct 5 ms 4312 KB Correct answer: answer = 9866346457
106 Correct 5 ms 4284 KB Correct answer: answer = 3327720949
107 Correct 3 ms 4308 KB Correct answer: answer = 86064128360
108 Correct 6 ms 4308 KB Correct answer: answer = 12698259150
109 Correct 6 ms 4596 KB Correct answer: answer = 1185259288
110 Correct 13 ms 5704 KB Correct answer: answer = 999889968863
111 Correct 11 ms 5704 KB Correct answer: answer = 999861384931
112 Correct 18 ms 5588 KB Correct answer: answer = 999811809929
113 Correct 13 ms 5668 KB Correct answer: answer = 999869756441
114 Correct 63 ms 9160 KB Correct answer: answer = 1700000000
115 Correct 50 ms 9212 KB Correct answer: answer = 131666670
116 Correct 16 ms 5880 KB Correct answer: answer = 89478486
117 Correct 15 ms 5924 KB Correct answer: answer = 4971040
118 Correct 16 ms 5852 KB Correct answer: answer = 2711494
119 Correct 57 ms 9208 KB Correct answer: answer = 25252530
120 Correct 45 ms 9160 KB Correct answer: answer = 62500000
121 Correct 73 ms 9192 KB Correct answer: answer = 333175097780
122 Correct 76 ms 9200 KB Correct answer: answer = 33121180179
123 Correct 83 ms 9128 KB Correct answer: answer = 9802314015
124 Correct 54 ms 9200 KB Correct answer: answer = 32567551
125 Correct 48 ms 9224 KB Correct answer: answer = 997525000000
126 Correct 80 ms 9024 KB Correct answer: answer = 752723538884
127 Correct 10 ms 5576 KB Correct answer: answer = 1000000000000
128 Correct 11 ms 5704 KB Correct answer: answer = 999978000121
129 Correct 12 ms 5708 KB Correct answer: answer = 745986144735
130 Correct 8 ms 5216 KB Correct answer: answer = 2
131 Correct 58 ms 9208 KB Correct answer: answer = 277966670
132 Correct 56 ms 9172 KB Correct answer: answer = 2500900082
133 Correct 19 ms 6092 KB Correct answer: answer = 301248349636
134 Correct 31 ms 6788 KB Correct answer: answer = 14118891
135 Correct 11 ms 5600 KB Correct answer: answer = 14384977265
136 Correct 11 ms 5712 KB Correct answer: answer = 3681368330
137 Correct 13 ms 5704 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Correct answer: answer = 4
2 Correct 2 ms 4180 KB Correct answer: answer = 4
3 Correct 2 ms 4180 KB Correct answer: answer = 4
4 Correct 2 ms 4180 KB Correct answer: answer = 12
5 Correct 2 ms 4180 KB Correct answer: answer = 52
6 Correct 2 ms 4180 KB Correct answer: answer = 210
7 Correct 2 ms 4180 KB Correct answer: answer = 88
8 Correct 2 ms 4180 KB Correct answer: answer = 7696
9 Correct 2 ms 4180 KB Correct answer: answer = 1
10 Correct 2 ms 4180 KB Correct answer: answer = 2374
11 Correct 2 ms 4180 KB Correct answer: answer = 9502
12 Correct 2 ms 4176 KB Correct answer: answer = 49
13 Correct 2 ms 4180 KB Correct answer: answer = 151
14 Correct 2 ms 4180 KB Correct answer: answer = 7550
15 Correct 2 ms 4180 KB Correct answer: answer = 7220
16 Correct 2 ms 4180 KB Correct answer: answer = 7550
17 Correct 2 ms 4180 KB Correct answer: answer = 10000
18 Correct 2 ms 4232 KB Correct answer: answer = 10000
19 Correct 2 ms 4220 KB Correct answer: answer = 624
20 Correct 2 ms 4180 KB Correct answer: answer = 10000
21 Correct 2 ms 4180 KB Correct answer: answer = 1
22 Correct 2 ms 4180 KB Correct answer: answer = 4
23 Correct 2 ms 4180 KB Correct answer: answer = 1
24 Correct 2 ms 4180 KB Correct answer: answer = 5
25 Correct 2 ms 4180 KB Correct answer: answer = 41
26 Correct 2 ms 4180 KB Correct answer: answer = 71923
27 Correct 2 ms 4180 KB Correct answer: answer = 77137
28 Correct 2 ms 4180 KB Correct answer: answer = 764
29 Correct 2 ms 4272 KB Correct answer: answer = 250000
30 Correct 3 ms 4180 KB Correct answer: answer = 500
31 Correct 2 ms 4180 KB Correct answer: answer = 32
32 Correct 2 ms 4180 KB Correct answer: answer = 130050
33 Correct 2 ms 4180 KB Correct answer: answer = 5110
34 Correct 2 ms 4180 KB Correct answer: answer = 2626
35 Correct 2 ms 4180 KB Correct answer: answer = 796
36 Correct 2 ms 4180 KB Correct answer: answer = 7580
37 Correct 3 ms 4180 KB Correct answer: answer = 1904
38 Correct 2 ms 4180 KB Correct answer: answer = 996004
39 Correct 2 ms 4180 KB Correct answer: answer = 38817
40 Correct 2 ms 4180 KB Correct answer: answer = 4096
41 Correct 2 ms 4180 KB Correct answer: answer = 1
42 Correct 2 ms 4180 KB Correct answer: answer = 1
43 Correct 2 ms 4180 KB Correct answer: answer = 2040
44 Correct 2 ms 4180 KB Correct answer: answer = 2
45 Correct 2 ms 4180 KB Correct answer: answer = 4
46 Correct 2 ms 4236 KB Correct answer: answer = 9
47 Correct 2 ms 4180 KB Correct answer: answer = 9
48 Correct 2 ms 4176 KB Correct answer: answer = 21
49 Correct 2 ms 4180 KB Correct answer: answer = 71
50 Correct 2 ms 4180 KB Correct answer: answer = 77
51 Correct 2 ms 4180 KB Correct answer: answer = 400
52 Correct 3 ms 4180 KB Correct answer: answer = 996004
53 Correct 2 ms 4180 KB Correct answer: answer = 997310
54 Correct 2 ms 4180 KB Correct answer: answer = 990781
55 Correct 2 ms 4180 KB Correct answer: answer = 996545
56 Correct 2 ms 4180 KB Correct answer: answer = 484
57 Correct 2 ms 4180 KB Correct answer: answer = 484
58 Correct 2 ms 4180 KB Correct answer: answer = 63501
59 Correct 2 ms 4180 KB Correct answer: answer = 323501
60 Correct 2 ms 4180 KB Correct answer: answer = 752500
61 Correct 2 ms 4180 KB Correct answer: answer = 761480
62 Correct 2 ms 4180 KB Correct answer: answer = 758932
63 Correct 2 ms 4180 KB Correct answer: answer = 1000000
64 Correct 2 ms 4180 KB Correct answer: answer = 750500
65 Correct 2 ms 4240 KB Correct answer: answer = 1000000
66 Correct 2 ms 4180 KB Correct answer: answer = 250000
67 Correct 2 ms 4180 KB Correct answer: answer = 250000
68 Correct 2 ms 4180 KB Correct answer: answer = 1000000
69 Correct 2 ms 4180 KB Correct answer: answer = 994009
70 Correct 2 ms 4180 KB Correct answer: answer = 59315
71 Correct 2 ms 4180 KB Correct answer: answer = 25454
72 Correct 2 ms 4180 KB Correct answer: answer = 1504
73 Correct 2 ms 4180 KB Correct answer: answer = 37486
74 Correct 2 ms 4180 KB Correct answer: answer = 4284
75 Correct 2 ms 4180 KB Correct answer: answer = 158008
76 Correct 2 ms 4180 KB Correct answer: answer = 51860
77 Correct 2 ms 4180 KB Correct answer: answer = 12985
78 Correct 3 ms 4180 KB Correct answer: answer = 997864126212
79 Correct 3 ms 4180 KB Correct answer: answer = 998608411647
80 Correct 3 ms 4180 KB Correct answer: answer = 995265560477
81 Correct 5 ms 4576 KB Correct answer: answer = 10125000
82 Correct 5 ms 4572 KB Correct answer: answer = 2291668
83 Correct 3 ms 4448 KB Correct answer: answer = 42388
84 Correct 5 ms 4436 KB Correct answer: answer = 10318
85 Correct 4 ms 4436 KB Correct answer: answer = 3416
86 Correct 9 ms 4692 KB Correct answer: answer = 331708193881
87 Correct 7 ms 4708 KB Correct answer: answer = 2861193756
88 Correct 10 ms 4684 KB Correct answer: answer = 114646930
89 Correct 5 ms 4612 KB Correct answer: answer = 9280921
90 Correct 6 ms 4684 KB Correct answer: answer = 999984053400
91 Correct 8 ms 4572 KB Correct answer: answer = 750935949134
92 Correct 5 ms 4232 KB Correct answer: answer = 1000000000000
93 Correct 3 ms 4288 KB Correct answer: answer = 998762383161
94 Correct 7 ms 4568 KB Correct answer: answer = 23017412908
95 Correct 8 ms 4312 KB Correct answer: answer = 728143410622
96 Correct 4 ms 4308 KB Correct answer: answer = 2
97 Correct 6 ms 4556 KB Correct answer: answer = 1824916
98 Correct 7 ms 4628 KB Correct answer: answer = 10680029
99 Correct 7 ms 4620 KB Correct answer: answer = 18351700
100 Correct 6 ms 4576 KB Correct answer: answer = 16040026
101 Correct 4 ms 4300 KB Correct answer: answer = 253968628325
102 Correct 4 ms 4576 KB Correct answer: answer = 10267
103 Correct 6 ms 4692 KB Correct answer: answer = 2582408
104 Correct 7 ms 4296 KB Correct answer: answer = 78024964781
105 Correct 5 ms 4312 KB Correct answer: answer = 9866346457
106 Correct 5 ms 4284 KB Correct answer: answer = 3327720949
107 Correct 3 ms 4308 KB Correct answer: answer = 86064128360
108 Correct 6 ms 4308 KB Correct answer: answer = 12698259150
109 Correct 6 ms 4596 KB Correct answer: answer = 1185259288
110 Correct 13 ms 5704 KB Correct answer: answer = 999889968863
111 Correct 11 ms 5704 KB Correct answer: answer = 999861384931
112 Correct 18 ms 5588 KB Correct answer: answer = 999811809929
113 Correct 13 ms 5668 KB Correct answer: answer = 999869756441
114 Correct 63 ms 9160 KB Correct answer: answer = 1700000000
115 Correct 50 ms 9212 KB Correct answer: answer = 131666670
116 Correct 16 ms 5880 KB Correct answer: answer = 89478486
117 Correct 15 ms 5924 KB Correct answer: answer = 4971040
118 Correct 16 ms 5852 KB Correct answer: answer = 2711494
119 Correct 57 ms 9208 KB Correct answer: answer = 25252530
120 Correct 45 ms 9160 KB Correct answer: answer = 62500000
121 Correct 73 ms 9192 KB Correct answer: answer = 333175097780
122 Correct 76 ms 9200 KB Correct answer: answer = 33121180179
123 Correct 83 ms 9128 KB Correct answer: answer = 9802314015
124 Correct 54 ms 9200 KB Correct answer: answer = 32567551
125 Correct 48 ms 9224 KB Correct answer: answer = 997525000000
126 Correct 80 ms 9024 KB Correct answer: answer = 752723538884
127 Correct 10 ms 5576 KB Correct answer: answer = 1000000000000
128 Correct 11 ms 5704 KB Correct answer: answer = 999978000121
129 Correct 12 ms 5708 KB Correct answer: answer = 745986144735
130 Correct 8 ms 5216 KB Correct answer: answer = 2
131 Correct 58 ms 9208 KB Correct answer: answer = 277966670
132 Correct 56 ms 9172 KB Correct answer: answer = 2500900082
133 Correct 19 ms 6092 KB Correct answer: answer = 301248349636
134 Correct 31 ms 6788 KB Correct answer: answer = 14118891
135 Correct 11 ms 5600 KB Correct answer: answer = 14384977265
136 Correct 11 ms 5712 KB Correct answer: answer = 3681368330
137 Correct 13 ms 5704 KB Correct answer: answer = 2720316816
138 Correct 20 ms 7132 KB Correct answer: answer = 999976000144
139 Correct 20 ms 7108 KB Correct answer: answer = 999856102410
140 Correct 20 ms 7112 KB Correct answer: answer = 999958401531
141 Correct 20 ms 7108 KB Correct answer: answer = 999769649944
142 Correct 20 ms 7080 KB Correct answer: answer = 999874525918
143 Correct 102 ms 14032 KB Correct answer: answer = 6050000000
144 Correct 104 ms 14012 KB Correct answer: answer = 1112500000
145 Correct 68 ms 10660 KB Correct answer: answer = 4294967296
146 Correct 57 ms 10668 KB Correct answer: answer = 87652406
147 Correct 60 ms 10756 KB Correct answer: answer = 6297664
148 Correct 57 ms 10696 KB Correct answer: answer = 196612
149 Correct 93 ms 14036 KB Correct answer: answer = 15015100
150 Correct 85 ms 14008 KB Correct answer: answer = 25000000
151 Correct 162 ms 13876 KB Correct answer: answer = 333230209550
152 Correct 158 ms 13860 KB Correct answer: answer = 917123769
153 Correct 139 ms 13984 KB Correct answer: answer = 95162
154 Correct 98 ms 14000 KB Correct answer: answer = 382616191
155 Correct 93 ms 14108 KB Correct answer: answer = 990033333400
156 Correct 101 ms 14100 KB Correct answer: answer = 990000100000
157 Correct 135 ms 13104 KB Correct answer: answer = 749998188180
158 Correct 21 ms 6976 KB Correct answer: answer = 1000000000000
159 Correct 20 ms 7108 KB Correct answer: answer = 999988000036
160 Correct 25 ms 7096 KB Correct answer: answer = 744929274393
161 Correct 14 ms 6092 KB Correct answer: answer = 2
162 Correct 90 ms 13992 KB Correct answer: answer = 1300024
163 Correct 100 ms 14004 KB Correct answer: answer = 5000700010
164 Correct 38 ms 7988 KB Correct answer: answer = 354997100800
165 Correct 65 ms 9176 KB Correct answer: answer = 257000
166 Correct 63 ms 9260 KB Correct answer: answer = 3765323
167 Correct 57 ms 9264 KB Correct answer: answer = 1525903
168 Correct 19 ms 7092 KB Correct answer: answer = 67618137730
169 Correct 19 ms 7112 KB Correct answer: answer = 12656680171
170 Correct 26 ms 7372 KB Correct answer: answer = 579831736
171 Correct 58 ms 9140 KB Correct answer: answer = 23605611
172 Correct 26 ms 7428 KB Correct answer: answer = 7052481200
173 Correct 28 ms 7988 KB Correct answer: answer = 1314039500
174 Correct 35 ms 8672 KB Correct answer: answer = 302484000
175 Correct 68 ms 11388 KB Correct answer: answer = 52348480