oj.uz

Submission #56856

# Submission time Handle Problem Language Result Execution time Memory
56856 2018-07-12T23:04:22 Z kingpig9 Aliens (IOI16_aliens) C++11
100 / 100
 235 ms 70524 KB 
//based off of koosaga...why does he do it DOUBLE?
#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 10;
const int MAXM = 1e6 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

ll sqr (ll x) {
	return x * x;
}

template<class T>
void setmin (T &a, T b) {
	if (b < a) {
		a = b;
	}
}

template<class T>
void setmax (T &a, T b) {
	if (a < b) {
		a = b;
	}
}

int N, M, K;
int mxy[MAXM];
ll X[MAXN], Y[MAXN];

//line: 
struct line {
	ll m, b;
	int id;
	line (ll _m, ll _b, int _id) : m(_m), b(_b), id(_id) {}
	ll val (ll x) const {
		return m * x + b;
	}

#warning Is using fraction really enough? Or will it possibly
	pll intersect (const line &a) const {
		//careful, might have to change to double
		pll p(b - a.b, a.m - m);
		if (p.se < 0) {
			p.fi *= -1;
			p.se *= -1;
		}
		return p;
	}
};

int compare (pll p1, pll p2) {
	//p1.fi * p2.se, p1.se * p2.fi
#warning do we need int128 here to compare? int128 might not even be supported in some places
	ll ltval = p1.fi * p2.se, rtval = p1.se * p2.fi;
	if (ltval < rtval) {
		return -1;
	} else if (ltval == rtval) {
		return 0;
	} else {
		return 1;
	}
}

struct convex {
	vector<line> hull;
	int ptr;
	ll x;
	convex() : hull(), ptr(), x(LLONG_MIN) {}
	void clear() {
		hull.clear();
		ptr = 0;
		x = LLONG_MIN;
	}
	void insert (line t) {
		if (hull.empty()) {
			hull.push_back(t);
			return;
		}
		line bk = hull.back();
		assert(bk.m <= t.m);
		if (bk.m == t.m && t.b <= bk.b) {
			return;
		}
		bool curerase = false;
		while (hull.size() >= 2) {
			int hsiz = hull.size();
			line l2 = hull[hsiz - 2];
			pll ph = l2.intersect(hull.back()), pt = l2.intersect(t);
			if (compare(pt, ph) <= 0) {
				if (hsiz == ptr + 1) {
					curerase = true;
				}
				hull.pop_back();
			} else {
				break;
			}
		}
		if (curerase) {
			ptr = int(hull.size()) - 1;
		}
		hull.push_back(t);
	}
	line query (ll t) {
		assert(t >= x);
		for (; ptr + 1 < hull.size(); ptr++) {
			if (hull[ptr].val(t) > hull[ptr + 1].val(t)) {
				break;
			}
		}
		x = t;
		return hull[ptr];
	}
} cht;

ll dp[MAXN];
int use[MAXN];

void moo (ll cost) {
	cht.clear();

	dp[0] = 0;
	use[0] = 0;

	for (int i = 1; i <= N; i++) {
		cht.insert(line(4 * X[i], -(2 * sqr(X[i]) + dp[i - 1]), i - 1));
		line lq = cht.query(Y[i]);
		dp[i] = 2 * sqr(Y[i]) - lq.val(Y[i]) + cost;
		if (i != N) {
			dp[i] -= 2 * sqr(max(0ll, Y[i] - X[i + 1]));
		}

		use[i] = use[lq.id] + 1;
	}
}

ll take_photos (int nnn, int mmm, int kkk, vector<int> rrr, vector<int> ccc) {
	N = nnn;
	M = mmm;
	K = kkk;

	//R, C
	fillchar(mxy, -1);
	for (int i = 0; i < N; i++) {
		int x = rrr[i], y = ccc[i];
		if (x > y) {
			swap(x, y);
		}
		setmax(mxy[x], y);
	}

	N = 0;
	for (int x = 0; x < M; x++) {
		int y = mxy[x];
		if (y == -1) {
			continue;
		}

		if (N == 0 || Y[N] < y) {
			N++;
			X[N] = x - 1;	//better for the algebra.
			Y[N] = y;
		}
	}

	setmin(K, N);	//IMPORTANT!!! Note: N is adjusted. Therefore, it may not be true that K <= N -- need to do it again.
	ll lo = 0, hi = 2e12;
	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		moo(2 * mid + 1);
		if (use[N] <= K) {
			hi = mid;
		} else {
			lo = mid;
		}
	}

	moo(2 * hi);
	//debug("hi = %lld. use[N] = %d\n", hi, use[N]);
	return dp[N] / 2 - hi * K;
}

Compilation message

aliens.cpp:49:2: warning: #warning Is using fraction really enough? Or will it possibly [-Wcpp]
 #warning Is using fraction really enough? Or will it possibly
  ^~~~~~~
aliens.cpp:63:2: warning: #warning do we need int128 here to compare? int128 might not even be supported in some places [-Wcpp]
 #warning do we need int128 here to compare? int128 might not even be supported in some places
  ^~~~~~~
aliens.cpp: In member function 'line convex::query(ll)':
aliens.cpp:115:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; ptr + 1 < hull.size(); ptr++) {
          ~~~~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4324 KB Correct answer: answer = 4
3 Correct 6 ms 4324 KB Correct answer: answer = 4
4 Correct 6 ms 4400 KB Correct answer: answer = 12
5 Correct 5 ms 4400 KB Correct answer: answer = 52
6 Correct 6 ms 4400 KB Correct answer: answer = 210
7 Correct 5 ms 4400 KB Correct answer: answer = 88
8 Correct 4 ms 4400 KB Correct answer: answer = 7696
9 Correct 9 ms 4400 KB Correct answer: answer = 1
10 Correct 5 ms 4400 KB Correct answer: answer = 2374
11 Correct 5 ms 4400 KB Correct answer: answer = 9502
12 Correct 6 ms 4572 KB Correct answer: answer = 49
13 Correct 7 ms 4572 KB Correct answer: answer = 151
14 Correct 5 ms 4572 KB Correct answer: answer = 7550
15 Correct 6 ms 4572 KB Correct answer: answer = 7220
16 Correct 6 ms 4572 KB Correct answer: answer = 7550
17 Correct 6 ms 4572 KB Correct answer: answer = 10000
18 Correct 7 ms 4572 KB Correct answer: answer = 10000
19 Correct 5 ms 4592 KB Correct answer: answer = 624
20 Correct 6 ms 4592 KB Correct answer: answer = 10000
21 Correct 6 ms 4592 KB Correct answer: answer = 1
22 Correct 7 ms 4592 KB Correct answer: answer = 4
23 Correct 5 ms 4592 KB Correct answer: answer = 1
24 Correct 5 ms 4592 KB Correct answer: answer = 5
25 Correct 5 ms 4592 KB Correct answer: answer = 41
26 Correct 5 ms 4592 KB Correct answer: answer = 71923
27 Correct 5 ms 4592 KB Correct answer: answer = 77137
28 Correct 5 ms 4604 KB Correct answer: answer = 764
29 Correct 5 ms 4604 KB Correct answer: answer = 250000
30 Correct 5 ms 4608 KB Correct answer: answer = 500
31 Correct 7 ms 4608 KB Correct answer: answer = 32
32 Correct 5 ms 4680 KB Correct answer: answer = 130050
33 Correct 5 ms 4688 KB Correct answer: answer = 5110
34 Correct 5 ms 4688 KB Correct answer: answer = 2626
35 Correct 5 ms 4688 KB Correct answer: answer = 796
36 Correct 5 ms 4696 KB Correct answer: answer = 7580
37 Correct 5 ms 4700 KB Correct answer: answer = 1904
38 Correct 6 ms 4700 KB Correct answer: answer = 996004
39 Correct 7 ms 4700 KB Correct answer: answer = 38817
40 Correct 6 ms 4700 KB Correct answer: answer = 4096
41 Correct 7 ms 4700 KB Correct answer: answer = 1
42 Correct 7 ms 4700 KB Correct answer: answer = 1
43 Correct 7 ms 4724 KB Correct answer: answer = 2040
44 Correct 7 ms 4724 KB Correct answer: answer = 2
45 Correct 6 ms 4732 KB Correct answer: answer = 4
46 Correct 6 ms 4732 KB Correct answer: answer = 9
47 Correct 7 ms 4736 KB Correct answer: answer = 9
48 Correct 6 ms 4736 KB Correct answer: answer = 21
49 Correct 6 ms 4744 KB Correct answer: answer = 71
50 Correct 6 ms 4748 KB Correct answer: answer = 77
51 Correct 7 ms 4752 KB Correct answer: answer = 400
52 Correct 6 ms 4756 KB Correct answer: answer = 996004
53 Correct 7 ms 4760 KB Correct answer: answer = 997310
54 Correct 6 ms 4764 KB Correct answer: answer = 990781
55 Correct 6 ms 4768 KB Correct answer: answer = 996545
56 Correct 6 ms 4772 KB Correct answer: answer = 484
57 Correct 5 ms 4776 KB Correct answer: answer = 484
58 Correct 5 ms 4908 KB Correct answer: answer = 63501
59 Correct 5 ms 4912 KB Correct answer: answer = 323501
60 Correct 7 ms 5036 KB Correct answer: answer = 752500
61 Correct 7 ms 5036 KB Correct answer: answer = 761480
62 Correct 8 ms 5036 KB Correct answer: answer = 758932
63 Correct 7 ms 5036 KB Correct answer: answer = 1000000
64 Correct 7 ms 5036 KB Correct answer: answer = 750500
65 Correct 6 ms 5036 KB Correct answer: answer = 1000000
66 Correct 6 ms 5036 KB Correct answer: answer = 250000
67 Correct 8 ms 5036 KB Correct answer: answer = 250000
68 Correct 6 ms 5036 KB Correct answer: answer = 1000000
69 Correct 6 ms 5036 KB Correct answer: answer = 994009
70 Correct 7 ms 5036 KB Correct answer: answer = 59315
71 Correct 6 ms 5036 KB Correct answer: answer = 25454
72 Correct 6 ms 5036 KB Correct answer: answer = 1504
73 Correct 5 ms 5036 KB Correct answer: answer = 37486
74 Correct 6 ms 5036 KB Correct answer: answer = 4284
75 Correct 5 ms 5036 KB Correct answer: answer = 158008
76 Correct 6 ms 5036 KB Correct answer: answer = 51860
77 Correct 5 ms 5036 KB Correct answer: answer = 12985
78 Correct 8 ms 5036 KB Correct answer: answer = 997864126212
79 Correct 8 ms 5052 KB Correct answer: answer = 998608411647
80 Correct 8 ms 5124 KB Correct answer: answer = 995265560477
81 Correct 10 ms 5360 KB Correct answer: answer = 10125000
82 Correct 10 ms 5492 KB Correct answer: answer = 2291668
83 Correct 8 ms 5548 KB Correct answer: answer = 42388
84 Correct 10 ms 5548 KB Correct answer: answer = 10318
85 Correct 8 ms 5548 KB Correct answer: answer = 3416
86 Correct 12 ms 5548 KB Correct answer: answer = 331708193881
87 Correct 16 ms 5568 KB Correct answer: answer = 2861193756
88 Correct 13 ms 5752 KB Correct answer: answer = 114646930
89 Correct 12 ms 5808 KB Correct answer: answer = 9280921
90 Correct 10 ms 5848 KB Correct answer: answer = 999984053400
91 Correct 14 ms 5896 KB Correct answer: answer = 750935949134
92 Correct 8 ms 5896 KB Correct answer: answer = 1000000000000
93 Correct 9 ms 5896 KB Correct answer: answer = 998762383161
94 Correct 15 ms 6072 KB Correct answer: answer = 23017412908
95 Correct 8 ms 6072 KB Correct answer: answer = 728143410622
96 Correct 8 ms 6072 KB Correct answer: answer = 2
97 Correct 12 ms 6232 KB Correct answer: answer = 1824916
98 Correct 11 ms 6272 KB Correct answer: answer = 10680029
99 Correct 12 ms 6320 KB Correct answer: answer = 18351700
100 Correct 14 ms 6320 KB Correct answer: answer = 16040026
101 Correct 9 ms 6320 KB Correct answer: answer = 253968628325
102 Correct 8 ms 6328 KB Correct answer: answer = 10267
103 Correct 12 ms 6480 KB Correct answer: answer = 2582408
104 Correct 7 ms 6480 KB Correct answer: answer = 78024964781
105 Correct 9 ms 6480 KB Correct answer: answer = 9866346457
106 Correct 9 ms 6480 KB Correct answer: answer = 3327720949
107 Correct 12 ms 6480 KB Correct answer: answer = 86064128360
108 Correct 9 ms 6628 KB Correct answer: answer = 12698259150
109 Correct 16 ms 6812 KB Correct answer: answer = 1185259288

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4324 KB Correct answer: answer = 4
3 Correct 6 ms 4324 KB Correct answer: answer = 4
4 Correct 6 ms 4400 KB Correct answer: answer = 12
5 Correct 5 ms 4400 KB Correct answer: answer = 52
6 Correct 6 ms 4400 KB Correct answer: answer = 210
7 Correct 5 ms 4400 KB Correct answer: answer = 88
8 Correct 4 ms 4400 KB Correct answer: answer = 7696
9 Correct 9 ms 4400 KB Correct answer: answer = 1
10 Correct 5 ms 4400 KB Correct answer: answer = 2374
11 Correct 5 ms 4400 KB Correct answer: answer = 9502
12 Correct 6 ms 4572 KB Correct answer: answer = 49
13 Correct 7 ms 4572 KB Correct answer: answer = 151
14 Correct 5 ms 4572 KB Correct answer: answer = 7550
15 Correct 6 ms 4572 KB Correct answer: answer = 7220
16 Correct 6 ms 4572 KB Correct answer: answer = 7550
17 Correct 6 ms 4572 KB Correct answer: answer = 10000
18 Correct 7 ms 4572 KB Correct answer: answer = 10000
19 Correct 5 ms 4592 KB Correct answer: answer = 624
20 Correct 6 ms 4592 KB Correct answer: answer = 10000
21 Correct 6 ms 4592 KB Correct answer: answer = 1
22 Correct 7 ms 4592 KB Correct answer: answer = 4
23 Correct 5 ms 4592 KB Correct answer: answer = 1
24 Correct 5 ms 4592 KB Correct answer: answer = 5
25 Correct 5 ms 4592 KB Correct answer: answer = 41
26 Correct 5 ms 4592 KB Correct answer: answer = 71923
27 Correct 5 ms 4592 KB Correct answer: answer = 77137
28 Correct 5 ms 4604 KB Correct answer: answer = 764
29 Correct 5 ms 4604 KB Correct answer: answer = 250000
30 Correct 5 ms 4608 KB Correct answer: answer = 500
31 Correct 7 ms 4608 KB Correct answer: answer = 32
32 Correct 5 ms 4680 KB Correct answer: answer = 130050
33 Correct 5 ms 4688 KB Correct answer: answer = 5110
34 Correct 5 ms 4688 KB Correct answer: answer = 2626
35 Correct 5 ms 4688 KB Correct answer: answer = 796
36 Correct 5 ms 4696 KB Correct answer: answer = 7580
37 Correct 5 ms 4700 KB Correct answer: answer = 1904
38 Correct 6 ms 4700 KB Correct answer: answer = 996004
39 Correct 7 ms 4700 KB Correct answer: answer = 38817
40 Correct 6 ms 4700 KB Correct answer: answer = 4096
41 Correct 7 ms 4700 KB Correct answer: answer = 1
42 Correct 7 ms 4700 KB Correct answer: answer = 1
43 Correct 7 ms 4724 KB Correct answer: answer = 2040
44 Correct 7 ms 4724 KB Correct answer: answer = 2
45 Correct 6 ms 4732 KB Correct answer: answer = 4
46 Correct 6 ms 4732 KB Correct answer: answer = 9
47 Correct 7 ms 4736 KB Correct answer: answer = 9
48 Correct 6 ms 4736 KB Correct answer: answer = 21
49 Correct 6 ms 4744 KB Correct answer: answer = 71
50 Correct 6 ms 4748 KB Correct answer: answer = 77
51 Correct 7 ms 4752 KB Correct answer: answer = 400
52 Correct 6 ms 4756 KB Correct answer: answer = 996004
53 Correct 7 ms 4760 KB Correct answer: answer = 997310
54 Correct 6 ms 4764 KB Correct answer: answer = 990781
55 Correct 6 ms 4768 KB Correct answer: answer = 996545
56 Correct 6 ms 4772 KB Correct answer: answer = 484
57 Correct 5 ms 4776 KB Correct answer: answer = 484
58 Correct 5 ms 4908 KB Correct answer: answer = 63501
59 Correct 5 ms 4912 KB Correct answer: answer = 323501
60 Correct 7 ms 5036 KB Correct answer: answer = 752500
61 Correct 7 ms 5036 KB Correct answer: answer = 761480
62 Correct 8 ms 5036 KB Correct answer: answer = 758932
63 Correct 7 ms 5036 KB Correct answer: answer = 1000000
64 Correct 7 ms 5036 KB Correct answer: answer = 750500
65 Correct 6 ms 5036 KB Correct answer: answer = 1000000
66 Correct 6 ms 5036 KB Correct answer: answer = 250000
67 Correct 8 ms 5036 KB Correct answer: answer = 250000
68 Correct 6 ms 5036 KB Correct answer: answer = 1000000
69 Correct 6 ms 5036 KB Correct answer: answer = 994009
70 Correct 7 ms 5036 KB Correct answer: answer = 59315
71 Correct 6 ms 5036 KB Correct answer: answer = 25454
72 Correct 6 ms 5036 KB Correct answer: answer = 1504
73 Correct 5 ms 5036 KB Correct answer: answer = 37486
74 Correct 6 ms 5036 KB Correct answer: answer = 4284
75 Correct 5 ms 5036 KB Correct answer: answer = 158008
76 Correct 6 ms 5036 KB Correct answer: answer = 51860
77 Correct 5 ms 5036 KB Correct answer: answer = 12985
78 Correct 8 ms 5036 KB Correct answer: answer = 997864126212
79 Correct 8 ms 5052 KB Correct answer: answer = 998608411647
80 Correct 8 ms 5124 KB Correct answer: answer = 995265560477
81 Correct 10 ms 5360 KB Correct answer: answer = 10125000
82 Correct 10 ms 5492 KB Correct answer: answer = 2291668
83 Correct 8 ms 5548 KB Correct answer: answer = 42388
84 Correct 10 ms 5548 KB Correct answer: answer = 10318
85 Correct 8 ms 5548 KB Correct answer: answer = 3416
86 Correct 12 ms 5548 KB Correct answer: answer = 331708193881
87 Correct 16 ms 5568 KB Correct answer: answer = 2861193756
88 Correct 13 ms 5752 KB Correct answer: answer = 114646930
89 Correct 12 ms 5808 KB Correct answer: answer = 9280921
90 Correct 10 ms 5848 KB Correct answer: answer = 999984053400
91 Correct 14 ms 5896 KB Correct answer: answer = 750935949134
92 Correct 8 ms 5896 KB Correct answer: answer = 1000000000000
93 Correct 9 ms 5896 KB Correct answer: answer = 998762383161
94 Correct 15 ms 6072 KB Correct answer: answer = 23017412908
95 Correct 8 ms 6072 KB Correct answer: answer = 728143410622
96 Correct 8 ms 6072 KB Correct answer: answer = 2
97 Correct 12 ms 6232 KB Correct answer: answer = 1824916
98 Correct 11 ms 6272 KB Correct answer: answer = 10680029
99 Correct 12 ms 6320 KB Correct answer: answer = 18351700
100 Correct 14 ms 6320 KB Correct answer: answer = 16040026
101 Correct 9 ms 6320 KB Correct answer: answer = 253968628325
102 Correct 8 ms 6328 KB Correct answer: answer = 10267
103 Correct 12 ms 6480 KB Correct answer: answer = 2582408
104 Correct 7 ms 6480 KB Correct answer: answer = 78024964781
105 Correct 9 ms 6480 KB Correct answer: answer = 9866346457
106 Correct 9 ms 6480 KB Correct answer: answer = 3327720949
107 Correct 12 ms 6480 KB Correct answer: answer = 86064128360
108 Correct 9 ms 6628 KB Correct answer: answer = 12698259150
109 Correct 16 ms 6812 KB Correct answer: answer = 1185259288
110 Correct 25 ms 8020 KB Correct answer: answer = 999889968863
111 Correct 37 ms 8696 KB Correct answer: answer = 999861384931
112 Correct 33 ms 9372 KB Correct answer: answer = 999811809929
113 Correct 41 ms 10048 KB Correct answer: answer = 999869756441
114 Correct 92 ms 12896 KB Correct answer: answer = 1700000000
115 Correct 66 ms 14228 KB Correct answer: answer = 131666670
116 Correct 26 ms 14228 KB Correct answer: answer = 89478486
117 Correct 25 ms 14228 KB Correct answer: answer = 4971040
118 Correct 29 ms 14228 KB Correct answer: answer = 2711494
119 Correct 83 ms 15312 KB Correct answer: answer = 25252530
120 Correct 79 ms 15880 KB Correct answer: answer = 62500000
121 Correct 101 ms 15880 KB Correct answer: answer = 333175097780
122 Correct 91 ms 15880 KB Correct answer: answer = 33121180179
123 Correct 102 ms 16292 KB Correct answer: answer = 9802314015
124 Correct 74 ms 18496 KB Correct answer: answer = 32567551
125 Correct 79 ms 19060 KB Correct answer: answer = 997525000000
126 Correct 85 ms 19060 KB Correct answer: answer = 752723538884
127 Correct 20 ms 19060 KB Correct answer: answer = 1000000000000
128 Correct 24 ms 19060 KB Correct answer: answer = 999978000121
129 Correct 21 ms 19060 KB Correct answer: answer = 745986144735
130 Correct 14 ms 19060 KB Correct answer: answer = 2
131 Correct 66 ms 22564 KB Correct answer: answer = 277966670
132 Correct 60 ms 22564 KB Correct answer: answer = 2500900082
133 Correct 31 ms 22564 KB Correct answer: answer = 301248349636
134 Correct 42 ms 22564 KB Correct answer: answer = 14118891
135 Correct 28 ms 22564 KB Correct answer: answer = 14384977265
136 Correct 28 ms 22564 KB Correct answer: answer = 3681368330
137 Correct 28 ms 23008 KB Correct answer: answer = 2720316816

Subtask #6
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4216 KB Correct answer: answer = 4
2 Correct 6 ms 4324 KB Correct answer: answer = 4
3 Correct 6 ms 4324 KB Correct answer: answer = 4
4 Correct 6 ms 4400 KB Correct answer: answer = 12
5 Correct 5 ms 4400 KB Correct answer: answer = 52
6 Correct 6 ms 4400 KB Correct answer: answer = 210
7 Correct 5 ms 4400 KB Correct answer: answer = 88
8 Correct 4 ms 4400 KB Correct answer: answer = 7696
9 Correct 9 ms 4400 KB Correct answer: answer = 1
10 Correct 5 ms 4400 KB Correct answer: answer = 2374
11 Correct 5 ms 4400 KB Correct answer: answer = 9502
12 Correct 6 ms 4572 KB Correct answer: answer = 49
13 Correct 7 ms 4572 KB Correct answer: answer = 151
14 Correct 5 ms 4572 KB Correct answer: answer = 7550
15 Correct 6 ms 4572 KB Correct answer: answer = 7220
16 Correct 6 ms 4572 KB Correct answer: answer = 7550
17 Correct 6 ms 4572 KB Correct answer: answer = 10000
18 Correct 7 ms 4572 KB Correct answer: answer = 10000
19 Correct 5 ms 4592 KB Correct answer: answer = 624
20 Correct 6 ms 4592 KB Correct answer: answer = 10000
21 Correct 6 ms 4592 KB Correct answer: answer = 1
22 Correct 7 ms 4592 KB Correct answer: answer = 4
23 Correct 5 ms 4592 KB Correct answer: answer = 1
24 Correct 5 ms 4592 KB Correct answer: answer = 5
25 Correct 5 ms 4592 KB Correct answer: answer = 41
26 Correct 5 ms 4592 KB Correct answer: answer = 71923
27 Correct 5 ms 4592 KB Correct answer: answer = 77137
28 Correct 5 ms 4604 KB Correct answer: answer = 764
29 Correct 5 ms 4604 KB Correct answer: answer = 250000
30 Correct 5 ms 4608 KB Correct answer: answer = 500
31 Correct 7 ms 4608 KB Correct answer: answer = 32
32 Correct 5 ms 4680 KB Correct answer: answer = 130050
33 Correct 5 ms 4688 KB Correct answer: answer = 5110
34 Correct 5 ms 4688 KB Correct answer: answer = 2626
35 Correct 5 ms 4688 KB Correct answer: answer = 796
36 Correct 5 ms 4696 KB Correct answer: answer = 7580
37 Correct 5 ms 4700 KB Correct answer: answer = 1904
38 Correct 6 ms 4700 KB Correct answer: answer = 996004
39 Correct 7 ms 4700 KB Correct answer: answer = 38817
40 Correct 6 ms 4700 KB Correct answer: answer = 4096
41 Correct 7 ms 4700 KB Correct answer: answer = 1
42 Correct 7 ms 4700 KB Correct answer: answer = 1
43 Correct 7 ms 4724 KB Correct answer: answer = 2040
44 Correct 7 ms 4724 KB Correct answer: answer = 2
45 Correct 6 ms 4732 KB Correct answer: answer = 4
46 Correct 6 ms 4732 KB Correct answer: answer = 9
47 Correct 7 ms 4736 KB Correct answer: answer = 9
48 Correct 6 ms 4736 KB Correct answer: answer = 21
49 Correct 6 ms 4744 KB Correct answer: answer = 71
50 Correct 6 ms 4748 KB Correct answer: answer = 77
51 Correct 7 ms 4752 KB Correct answer: answer = 400
52 Correct 6 ms 4756 KB Correct answer: answer = 996004
53 Correct 7 ms 4760 KB Correct answer: answer = 997310
54 Correct 6 ms 4764 KB Correct answer: answer = 990781
55 Correct 6 ms 4768 KB Correct answer: answer = 996545
56 Correct 6 ms 4772 KB Correct answer: answer = 484
57 Correct 5 ms 4776 KB Correct answer: answer = 484
58 Correct 5 ms 4908 KB Correct answer: answer = 63501
59 Correct 5 ms 4912 KB Correct answer: answer = 323501
60 Correct 7 ms 5036 KB Correct answer: answer = 752500
61 Correct 7 ms 5036 KB Correct answer: answer = 761480
62 Correct 8 ms 5036 KB Correct answer: answer = 758932
63 Correct 7 ms 5036 KB Correct answer: answer = 1000000
64 Correct 7 ms 5036 KB Correct answer: answer = 750500
65 Correct 6 ms 5036 KB Correct answer: answer = 1000000
66 Correct 6 ms 5036 KB Correct answer: answer = 250000
67 Correct 8 ms 5036 KB Correct answer: answer = 250000
68 Correct 6 ms 5036 KB Correct answer: answer = 1000000
69 Correct 6 ms 5036 KB Correct answer: answer = 994009
70 Correct 7 ms 5036 KB Correct answer: answer = 59315
71 Correct 6 ms 5036 KB Correct answer: answer = 25454
72 Correct 6 ms 5036 KB Correct answer: answer = 1504
73 Correct 5 ms 5036 KB Correct answer: answer = 37486
74 Correct 6 ms 5036 KB Correct answer: answer = 4284
75 Correct 5 ms 5036 KB Correct answer: answer = 158008
76 Correct 6 ms 5036 KB Correct answer: answer = 51860
77 Correct 5 ms 5036 KB Correct answer: answer = 12985
78 Correct 8 ms 5036 KB Correct answer: answer = 997864126212
79 Correct 8 ms 5052 KB Correct answer: answer = 998608411647
80 Correct 8 ms 5124 KB Correct answer: answer = 995265560477
81 Correct 10 ms 5360 KB Correct answer: answer = 10125000
82 Correct 10 ms 5492 KB Correct answer: answer = 2291668
83 Correct 8 ms 5548 KB Correct answer: answer = 42388
84 Correct 10 ms 5548 KB Correct answer: answer = 10318
85 Correct 8 ms 5548 KB Correct answer: answer = 3416
86 Correct 12 ms 5548 KB Correct answer: answer = 331708193881
87 Correct 16 ms 5568 KB Correct answer: answer = 2861193756
88 Correct 13 ms 5752 KB Correct answer: answer = 114646930
89 Correct 12 ms 5808 KB Correct answer: answer = 9280921
90 Correct 10 ms 5848 KB Correct answer: answer = 999984053400
91 Correct 14 ms 5896 KB Correct answer: answer = 750935949134
92 Correct 8 ms 5896 KB Correct answer: answer = 1000000000000
93 Correct 9 ms 5896 KB Correct answer: answer = 998762383161
94 Correct 15 ms 6072 KB Correct answer: answer = 23017412908
95 Correct 8 ms 6072 KB Correct answer: answer = 728143410622
96 Correct 8 ms 6072 KB Correct answer: answer = 2
97 Correct 12 ms 6232 KB Correct answer: answer = 1824916
98 Correct 11 ms 6272 KB Correct answer: answer = 10680029
99 Correct 12 ms 6320 KB Correct answer: answer = 18351700
100 Correct 14 ms 6320 KB Correct answer: answer = 16040026
101 Correct 9 ms 6320 KB Correct answer: answer = 253968628325
102 Correct 8 ms 6328 KB Correct answer: answer = 10267
103 Correct 12 ms 6480 KB Correct answer: answer = 2582408
104 Correct 7 ms 6480 KB Correct answer: answer = 78024964781
105 Correct 9 ms 6480 KB Correct answer: answer = 9866346457
106 Correct 9 ms 6480 KB Correct answer: answer = 3327720949
107 Correct 12 ms 6480 KB Correct answer: answer = 86064128360
108 Correct 9 ms 6628 KB Correct answer: answer = 12698259150
109 Correct 16 ms 6812 KB Correct answer: answer = 1185259288
110 Correct 25 ms 8020 KB Correct answer: answer = 999889968863
111 Correct 37 ms 8696 KB Correct answer: answer = 999861384931
112 Correct 33 ms 9372 KB Correct answer: answer = 999811809929
113 Correct 41 ms 10048 KB Correct answer: answer = 999869756441
114 Correct 92 ms 12896 KB Correct answer: answer = 1700000000
115 Correct 66 ms 14228 KB Correct answer: answer = 131666670
116 Correct 26 ms 14228 KB Correct answer: answer = 89478486
117 Correct 25 ms 14228 KB Correct answer: answer = 4971040
118 Correct 29 ms 14228 KB Correct answer: answer = 2711494
119 Correct 83 ms 15312 KB Correct answer: answer = 25252530
120 Correct 79 ms 15880 KB Correct answer: answer = 62500000
121 Correct 101 ms 15880 KB Correct answer: answer = 333175097780
122 Correct 91 ms 15880 KB Correct answer: answer = 33121180179
123 Correct 102 ms 16292 KB Correct answer: answer = 9802314015
124 Correct 74 ms 18496 KB Correct answer: answer = 32567551
125 Correct 79 ms 19060 KB Correct answer: answer = 997525000000
126 Correct 85 ms 19060 KB Correct answer: answer = 752723538884
127 Correct 20 ms 19060 KB Correct answer: answer = 1000000000000
128 Correct 24 ms 19060 KB Correct answer: answer = 999978000121
129 Correct 21 ms 19060 KB Correct answer: answer = 745986144735
130 Correct 14 ms 19060 KB Correct answer: answer = 2
131 Correct 66 ms 22564 KB Correct answer: answer = 277966670
132 Correct 60 ms 22564 KB Correct answer: answer = 2500900082
133 Correct 31 ms 22564 KB Correct answer: answer = 301248349636
134 Correct 42 ms 22564 KB Correct answer: answer = 14118891
135 Correct 28 ms 22564 KB Correct answer: answer = 14384977265
136 Correct 28 ms 22564 KB Correct answer: answer = 3681368330
137 Correct 28 ms 23008 KB Correct answer: answer = 2720316816
138 Correct 52 ms 25088 KB Correct answer: answer = 999976000144
139 Correct 62 ms 26436 KB Correct answer: answer = 999856102410
140 Correct 63 ms 27784 KB Correct answer: answer = 999958401531
141 Correct 40 ms 29276 KB Correct answer: answer = 999769649944
142 Correct 52 ms 30512 KB Correct answer: answer = 999874525918
143 Correct 148 ms 36224 KB Correct answer: answer = 6050000000
144 Correct 159 ms 38780 KB Correct answer: answer = 1112500000
145 Correct 92 ms 38780 KB Correct answer: answer = 4294967296
146 Correct 93 ms 38780 KB Correct answer: answer = 87652406
147 Correct 99 ms 38780 KB Correct answer: answer = 6297664
148 Correct 81 ms 38884 KB Correct answer: answer = 196612
149 Correct 121 ms 43092 KB Correct answer: answer = 15015100
150 Correct 167 ms 44232 KB Correct answer: answer = 25000000
151 Correct 179 ms 44232 KB Correct answer: answer = 333230209550
152 Correct 160 ms 44232 KB Correct answer: answer = 917123769
153 Correct 235 ms 48224 KB Correct answer: answer = 95162
154 Correct 143 ms 49380 KB Correct answer: answer = 382616191
155 Correct 181 ms 50824 KB Correct answer: answer = 990033333400
156 Correct 139 ms 51904 KB Correct answer: answer = 990000100000
157 Correct 170 ms 51904 KB Correct answer: answer = 749998188180
158 Correct 53 ms 51904 KB Correct answer: answer = 1000000000000
159 Correct 41 ms 51904 KB Correct answer: answer = 999988000036
160 Correct 37 ms 51904 KB Correct answer: answer = 744929274393
161 Correct 26 ms 51904 KB Correct answer: answer = 2
162 Correct 149 ms 58788 KB Correct answer: answer = 1300024
163 Correct 134 ms 58788 KB Correct answer: answer = 5000700010
164 Correct 53 ms 58788 KB Correct answer: answer = 354997100800
165 Correct 107 ms 58788 KB Correct answer: answer = 257000
166 Correct 79 ms 58788 KB Correct answer: answer = 3765323
167 Correct 96 ms 59456 KB Correct answer: answer = 1525903
168 Correct 44 ms 59456 KB Correct answer: answer = 67618137730
169 Correct 36 ms 59828 KB Correct answer: answer = 12656680171
170 Correct 51 ms 61468 KB Correct answer: answer = 579831736
171 Correct 71 ms 63904 KB Correct answer: answer = 23605611
172 Correct 63 ms 64260 KB Correct answer: answer = 7052481200
173 Correct 73 ms 66092 KB Correct answer: answer = 1314039500
174 Correct 68 ms 68012 KB Correct answer: answer = 302484000
175 Correct 127 ms 70524 KB Correct answer: answer = 52348480