oj.uz

Submission #292001

# Submission time Handle Problem Language Result Execution time Memory
292001 2020-09-06T07:28:47 Z Diuven Robogolf (ROI19_golf) C++11
100 / 100
 2360 ms 83300 KB 
// Created by Nikolay Budin

#ifdef LOCAL
#  define _GLIBCXX_DEBUG
#else
#  define cerr __get_ce
#endif
#include <bits/stdc++.h>
#define ff first
#define ss second
#define szof(x) ((int)x.size())

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef unsigned long long ull;
int const INF = (int)1e9 + 1e3;
ll const INFL = (ll)1e18 + 1e6;
#ifdef LOCAL
	mt19937 tw(9450189);
#else
	mt19937 tw(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
uniform_int_distribution<ll> ll_distr;
ll rnd(ll a, ll b) { return ll_distr(tw) % (b - a + 1) + a; }

const int MOD = 998244353;

struct cells_order {
	bool operator()(pii p1, pii p2) {
		return p1.ff - p1.ss < p2.ff - p2.ss || (p1.ff - p1.ss == p2.ff - p2.ss && p1.ff + p1.ss < p2.ff + p2.ss);
	}
};

void solve() {
	int h, w, n;
	cin >> h >> w >> n;
	int m = max(h, w);
	vector<set<pii, cells_order>> intr_cells(2);
	vector<set<int>> intr_diags(2);
	map<pii, int> inp;
	for (int i = 0; i < n; ++i) {
		int x, y, v;
		cin >> x >> y >> v;
		--y;
		x = m - x;
		inp[{x, y}] = v;
		for (int dx = 0; dx <= 2; ++dx) {
			for (int dy = -2; dy <= 0; ++dy) {
				if (abs(dx) + abs(dy) <= 2) {
					int nx = x + dx;
					int ny = y + dy;
					if (0 <= nx && nx < m && 0 <= ny && ny < m) {
						intr_cells[(nx + ny) & 1].insert({nx, ny});
						intr_diags[(nx + ny) & 1].insert(nx - ny);
					}
				}
			}
		}
	}

	int ans = 0;
	vector<pii> change;
	for (int q = 0; q < 2; ++q) {
		auto it = intr_cells[q].begin();
		auto it_diag = intr_diags[q].begin();
		ll sum = 0;
		unordered_map<int, int> arr;
		int prev = -INF;
		while (it_diag != intr_diags[q].end()) {
			int i = *it_diag;
			ans = (ans + (ll) (i - prev) / 2 * (sum % MOD)) % MOD;
			int l = abs(i);
			int r = m * 2 - 2 - abs(i);

			if (i > 1) {
				if (arr.count(l - 2)) {
					sum -= arr[l - 2];
				}
				if (arr.count(r + 2)) {
					sum -= arr[r + 2];
				}
			}

			change.clear();

			while (it != intr_cells[q].end() && it->ff - it->ss == i) {
				int x, y;
				tie(x, y) = *it;

				if (inp.count({x, y})) {
					change.push_back({x + y, inp[{x, y}]});
				} else {
					int val1;
					if (inp.count({x - 1, y})) {
						val1 = inp[{x - 1, y}];
					} else {
						val1 = max(arr.count(x + y) ? arr[x + y] : 0, arr.count(x + y - 2) ? arr[x + y - 2] : 0);
					}
					int val2;
					if (inp.count({x, y + 1})) {
						val2 = inp[{x, y + 1}];
					} else {
						val2 = max(arr.count(x + y) ? arr[x + y] : 0, arr.count(x + y + 2) ? arr[x + y + 2] : 0);
					}

					change.push_back({x + y, min(val1, val2)});
					if (x + y < m - 2) {
						intr_diags[q].insert(x + y + 2);
					} else if (x + y >= m + 1) {
						intr_diags[q].insert(m - 1 - (x + y - (m - 1) - 2));
					}
				}

				++it;
			}

			for (pii p : change) {
				if (l <= p.ff && p.ff <= r) {
					sum -= arr[p.ff];
				}

				arr[p.ff] = p.ss;

				if (l <= p.ff && p.ff <= r) {
					sum += arr[p.ff];
				}
			}


			prev = i;
			++it_diag;
		}

		ans = (ans + (ll) (((m & 1) == q ? m : m + 1) - prev) / 2 * (sum % MOD)) % MOD;
	}

	cout << (ans + MOD) % MOD << "\n";
}


int main() {
#ifdef LOCAL
	auto start_time = clock();
	cerr << setprecision(3) << fixed;
#endif
	cout << setprecision(15) << fixed;
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int test_count = 1;
	// cin >> test_count;
	for (int test = 1; test <= test_count; ++test) {
		solve();
	}
	
#ifdef LOCAL
	auto end_time = clock();
	cerr << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1039 ms 28920 KB Output is correct
11 Correct 1020 ms 28792 KB Output is correct
12 Correct 991 ms 28652 KB Output is correct
13 Correct 1028 ms 28292 KB Output is correct
14 Correct 1012 ms 23928 KB Output is correct
15 Correct 856 ms 24184 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 17 ms 1280 KB Output is correct
19 Correct 22 ms 1152 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 911 ms 24696 KB Output is correct
23 Correct 708 ms 18680 KB Output is correct
24 Correct 755 ms 20292 KB Output is correct
25 Correct 693 ms 19704 KB Output is correct
26 Correct 961 ms 25720 KB Output is correct
27 Correct 859 ms 23672 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 562 ms 24312 KB Output is correct
33 Correct 676 ms 29048 KB Output is correct
34 Correct 349 ms 16632 KB Output is correct
35 Correct 330 ms 15992 KB Output is correct
36 Correct 311 ms 15308 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 82 ms 4344 KB Output is correct
4 Correct 766 ms 29716 KB Output is correct
5 Correct 1256 ms 62448 KB Output is correct
6 Correct 1429 ms 73312 KB Output is correct
7 Correct 1465 ms 74488 KB Output is correct
8 Correct 889 ms 51652 KB Output is correct
9 Correct 1171 ms 61948 KB Output is correct
10 Correct 1490 ms 68960 KB Output is correct
11 Correct 1465 ms 72924 KB Output is correct
12 Correct 1497 ms 74524 KB Output is correct
13 Correct 1569 ms 72428 KB Output is correct
14 Correct 1403 ms 71084 KB Output is correct
15 Correct 1058 ms 46164 KB Output is correct
16 Correct 1064 ms 44156 KB Output is correct
17 Correct 1414 ms 69320 KB Output is correct
18 Correct 878 ms 37488 KB Output is correct
19 Correct 1028 ms 41764 KB Output is correct
20 Correct 924 ms 40012 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 460 ms 33624 KB Output is correct
27 Correct 565 ms 40060 KB Output is correct
28 Correct 305 ms 19704 KB Output is correct
29 Correct 293 ms 18936 KB Output is correct
30 Correct 285 ms 18168 KB Output is correct
31 Correct 337 ms 21624 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 18204 KB Output is correct
2 Correct 385 ms 18192 KB Output is correct
3 Correct 729 ms 27732 KB Output is correct
4 Correct 662 ms 27148 KB Output is correct
5 Correct 667 ms 27396 KB Output is correct
6 Correct 560 ms 22788 KB Output is correct
7 Correct 715 ms 27532 KB Output is correct
8 Correct 799 ms 27484 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1039 ms 28920 KB Output is correct
11 Correct 1020 ms 28792 KB Output is correct
12 Correct 991 ms 28652 KB Output is correct
13 Correct 1028 ms 28292 KB Output is correct
14 Correct 1012 ms 23928 KB Output is correct
15 Correct 856 ms 24184 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 17 ms 1280 KB Output is correct
19 Correct 22 ms 1152 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 911 ms 24696 KB Output is correct
23 Correct 708 ms 18680 KB Output is correct
24 Correct 755 ms 20292 KB Output is correct
25 Correct 693 ms 19704 KB Output is correct
26 Correct 961 ms 25720 KB Output is correct
27 Correct 859 ms 23672 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 562 ms 24312 KB Output is correct
33 Correct 676 ms 29048 KB Output is correct
34 Correct 349 ms 16632 KB Output is correct
35 Correct 330 ms 15992 KB Output is correct
36 Correct 311 ms 15308 KB Output is correct
37 Correct 1050 ms 28848 KB Output is correct
38 Correct 1016 ms 28812 KB Output is correct
39 Correct 1030 ms 28872 KB Output is correct
40 Correct 1092 ms 28712 KB Output is correct
41 Correct 914 ms 24648 KB Output is correct
42 Correct 709 ms 18672 KB Output is correct
43 Correct 775 ms 20368 KB Output is correct
44 Correct 759 ms 19576 KB Output is correct
45 Correct 977 ms 25792 KB Output is correct
46 Correct 901 ms 23716 KB Output is correct
47 Correct 7 ms 768 KB Output is correct
48 Correct 7 ms 768 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 46524 KB Output is correct
2 Correct 1514 ms 44608 KB Output is correct
3 Correct 1326 ms 42736 KB Output is correct
4 Correct 1330 ms 42824 KB Output is correct
5 Correct 45 ms 4728 KB Output is correct
6 Correct 146 ms 10896 KB Output is correct
7 Correct 952 ms 34664 KB Output is correct
8 Correct 866 ms 34488 KB Output is correct
9 Correct 1217 ms 41112 KB Output is correct
10 Correct 1048 ms 41232 KB Output is correct
11 Correct 1408 ms 41872 KB Output is correct
12 Correct 1126 ms 41868 KB Output is correct
13 Correct 1713 ms 42272 KB Output is correct
14 Correct 1392 ms 42312 KB Output is correct
15 Correct 882 ms 31308 KB Output is correct
16 Correct 718 ms 21368 KB Output is correct
17 Correct 808 ms 23972 KB Output is correct
18 Correct 708 ms 26600 KB Output is correct
19 Correct 989 ms 34680 KB Output is correct
20 Correct 821 ms 31096 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 572 ms 24312 KB Output is correct
23 Correct 689 ms 28924 KB Output is correct
24 Correct 909 ms 34168 KB Output is correct
25 Correct 98 ms 5880 KB Output is correct
26 Correct 128 ms 7416 KB Output is correct
27 Correct 145 ms 8312 KB Output is correct

Subtask #6
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1637 ms 46524 KB Output is correct
2 Correct 1514 ms 44608 KB Output is correct
3 Correct 1326 ms 42736 KB Output is correct
4 Correct 1330 ms 42824 KB Output is correct
5 Correct 45 ms 4728 KB Output is correct
6 Correct 146 ms 10896 KB Output is correct
7 Correct 952 ms 34664 KB Output is correct
8 Correct 866 ms 34488 KB Output is correct
9 Correct 1217 ms 41112 KB Output is correct
10 Correct 1048 ms 41232 KB Output is correct
11 Correct 1408 ms 41872 KB Output is correct
12 Correct 1126 ms 41868 KB Output is correct
13 Correct 1713 ms 42272 KB Output is correct
14 Correct 1392 ms 42312 KB Output is correct
15 Correct 882 ms 31308 KB Output is correct
16 Correct 718 ms 21368 KB Output is correct
17 Correct 808 ms 23972 KB Output is correct
18 Correct 708 ms 26600 KB Output is correct
19 Correct 989 ms 34680 KB Output is correct
20 Correct 821 ms 31096 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 572 ms 24312 KB Output is correct
23 Correct 689 ms 28924 KB Output is correct
24 Correct 909 ms 34168 KB Output is correct
25 Correct 98 ms 5880 KB Output is correct
26 Correct 128 ms 7416 KB Output is correct
27 Correct 145 ms 8312 KB Output is correct
28 Correct 2270 ms 83160 KB Output is correct
29 Correct 2045 ms 78328 KB Output is correct
30 Correct 1935 ms 75260 KB Output is correct
31 Correct 2013 ms 83220 KB Output is correct
32 Correct 1676 ms 83300 KB Output is correct
33 Correct 911 ms 32120 KB Output is correct
34 Correct 768 ms 21540 KB Output is correct
35 Correct 791 ms 23328 KB Output is correct
36 Correct 709 ms 35696 KB Output is correct
37 Correct 916 ms 39720 KB Output is correct
38 Correct 685 ms 33928 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1039 ms 28920 KB Output is correct
11 Correct 1020 ms 28792 KB Output is correct
12 Correct 991 ms 28652 KB Output is correct
13 Correct 1028 ms 28292 KB Output is correct
14 Correct 1012 ms 23928 KB Output is correct
15 Correct 856 ms 24184 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 17 ms 1280 KB Output is correct
19 Correct 22 ms 1152 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 911 ms 24696 KB Output is correct
23 Correct 708 ms 18680 KB Output is correct
24 Correct 755 ms 20292 KB Output is correct
25 Correct 693 ms 19704 KB Output is correct
26 Correct 961 ms 25720 KB Output is correct
27 Correct 859 ms 23672 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 562 ms 24312 KB Output is correct
33 Correct 676 ms 29048 KB Output is correct
34 Correct 349 ms 16632 KB Output is correct
35 Correct 330 ms 15992 KB Output is correct
36 Correct 311 ms 15308 KB Output is correct
37 Correct 380 ms 18204 KB Output is correct
38 Correct 385 ms 18192 KB Output is correct
39 Correct 729 ms 27732 KB Output is correct
40 Correct 662 ms 27148 KB Output is correct
41 Correct 667 ms 27396 KB Output is correct
42 Correct 560 ms 22788 KB Output is correct
43 Correct 715 ms 27532 KB Output is correct
44 Correct 799 ms 27484 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 0 ms 384 KB Output is correct
47 Correct 1637 ms 46524 KB Output is correct
48 Correct 1514 ms 44608 KB Output is correct
49 Correct 1326 ms 42736 KB Output is correct
50 Correct 1330 ms 42824 KB Output is correct
51 Correct 45 ms 4728 KB Output is correct
52 Correct 146 ms 10896 KB Output is correct
53 Correct 952 ms 34664 KB Output is correct
54 Correct 866 ms 34488 KB Output is correct
55 Correct 1217 ms 41112 KB Output is correct
56 Correct 1048 ms 41232 KB Output is correct
57 Correct 1408 ms 41872 KB Output is correct
58 Correct 1126 ms 41868 KB Output is correct
59 Correct 1713 ms 42272 KB Output is correct
60 Correct 1392 ms 42312 KB Output is correct
61 Correct 882 ms 31308 KB Output is correct
62 Correct 718 ms 21368 KB Output is correct
63 Correct 808 ms 23972 KB Output is correct
64 Correct 708 ms 26600 KB Output is correct
65 Correct 989 ms 34680 KB Output is correct
66 Correct 821 ms 31096 KB Output is correct
67 Correct 0 ms 384 KB Output is correct
68 Correct 572 ms 24312 KB Output is correct
69 Correct 689 ms 28924 KB Output is correct
70 Correct 909 ms 34168 KB Output is correct
71 Correct 98 ms 5880 KB Output is correct
72 Correct 128 ms 7416 KB Output is correct
73 Correct 145 ms 8312 KB Output is correct
74 Correct 1665 ms 46384 KB Output is correct
75 Correct 1490 ms 44468 KB Output is correct
76 Correct 1327 ms 42816 KB Output is correct
77 Correct 1345 ms 42708 KB Output is correct
78 Correct 43 ms 4728 KB Output is correct
79 Correct 134 ms 10984 KB Output is correct
80 Correct 911 ms 34604 KB Output is correct
81 Correct 808 ms 34580 KB Output is correct
82 Correct 1216 ms 41100 KB Output is correct
83 Correct 992 ms 41112 KB Output is correct
84 Correct 1421 ms 41876 KB Output is correct
85 Correct 1115 ms 41884 KB Output is correct
86 Correct 1601 ms 42168 KB Output is correct
87 Correct 1440 ms 42256 KB Output is correct
88 Correct 992 ms 31368 KB Output is correct
89 Correct 720 ms 21244 KB Output is correct
90 Correct 836 ms 24244 KB Output is correct
91 Correct 717 ms 26808 KB Output is correct
92 Correct 943 ms 35284 KB Output is correct
93 Correct 728 ms 29976 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1152 KB Output is correct
2 Correct 8 ms 1152 KB Output is correct
3 Correct 10 ms 1152 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 8 ms 1152 KB Output is correct
6 Correct 11 ms 1152 KB Output is correct
7 Correct 11 ms 1152 KB Output is correct
8 Correct 8 ms 1152 KB Output is correct
9 Correct 8 ms 1024 KB Output is correct
10 Correct 10 ms 1152 KB Output is correct
11 Correct 7 ms 896 KB Output is correct
12 Correct 6 ms 768 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 5 ms 768 KB Output is correct
16 Correct 4 ms 768 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 3 ms 640 KB Output is correct
20 Correct 5 ms 768 KB Output is correct
21 Correct 5 ms 768 KB Output is correct
22 Correct 2 ms 512 KB Output is correct
23 Correct 2 ms 512 KB Output is correct
24 Correct 2 ms 488 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1039 ms 28920 KB Output is correct
11 Correct 1020 ms 28792 KB Output is correct
12 Correct 991 ms 28652 KB Output is correct
13 Correct 1028 ms 28292 KB Output is correct
14 Correct 1012 ms 23928 KB Output is correct
15 Correct 856 ms 24184 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 17 ms 1280 KB Output is correct
19 Correct 22 ms 1152 KB Output is correct
20 Correct 2 ms 512 KB Output is correct
21 Correct 4 ms 640 KB Output is correct
22 Correct 911 ms 24696 KB Output is correct
23 Correct 708 ms 18680 KB Output is correct
24 Correct 755 ms 20292 KB Output is correct
25 Correct 693 ms 19704 KB Output is correct
26 Correct 961 ms 25720 KB Output is correct
27 Correct 859 ms 23672 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 562 ms 24312 KB Output is correct
33 Correct 676 ms 29048 KB Output is correct
34 Correct 349 ms 16632 KB Output is correct
35 Correct 330 ms 15992 KB Output is correct
36 Correct 311 ms 15308 KB Output is correct
37 Correct 380 ms 18204 KB Output is correct
38 Correct 385 ms 18192 KB Output is correct
39 Correct 729 ms 27732 KB Output is correct
40 Correct 662 ms 27148 KB Output is correct
41 Correct 667 ms 27396 KB Output is correct
42 Correct 560 ms 22788 KB Output is correct
43 Correct 715 ms 27532 KB Output is correct
44 Correct 799 ms 27484 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 0 ms 384 KB Output is correct
47 Correct 1 ms 384 KB Output is correct
48 Correct 1 ms 384 KB Output is correct
49 Correct 82 ms 4344 KB Output is correct
50 Correct 766 ms 29716 KB Output is correct
51 Correct 1256 ms 62448 KB Output is correct
52 Correct 1429 ms 73312 KB Output is correct
53 Correct 1465 ms 74488 KB Output is correct
54 Correct 889 ms 51652 KB Output is correct
55 Correct 1171 ms 61948 KB Output is correct
56 Correct 1490 ms 68960 KB Output is correct
57 Correct 1465 ms 72924 KB Output is correct
58 Correct 1497 ms 74524 KB Output is correct
59 Correct 1569 ms 72428 KB Output is correct
60 Correct 1403 ms 71084 KB Output is correct
61 Correct 1058 ms 46164 KB Output is correct
62 Correct 1064 ms 44156 KB Output is correct
63 Correct 1414 ms 69320 KB Output is correct
64 Correct 878 ms 37488 KB Output is correct
65 Correct 1028 ms 41764 KB Output is correct
66 Correct 924 ms 40012 KB Output is correct
67 Correct 1 ms 384 KB Output is correct
68 Correct 1 ms 384 KB Output is correct
69 Correct 1 ms 384 KB Output is correct
70 Correct 0 ms 384 KB Output is correct
71 Correct 0 ms 384 KB Output is correct
72 Correct 460 ms 33624 KB Output is correct
73 Correct 565 ms 40060 KB Output is correct
74 Correct 305 ms 19704 KB Output is correct
75 Correct 293 ms 18936 KB Output is correct
76 Correct 285 ms 18168 KB Output is correct
77 Correct 337 ms 21624 KB Output is correct
78 Correct 1050 ms 28848 KB Output is correct
79 Correct 1016 ms 28812 KB Output is correct
80 Correct 1030 ms 28872 KB Output is correct
81 Correct 1092 ms 28712 KB Output is correct
82 Correct 914 ms 24648 KB Output is correct
83 Correct 709 ms 18672 KB Output is correct
84 Correct 775 ms 20368 KB Output is correct
85 Correct 759 ms 19576 KB Output is correct
86 Correct 977 ms 25792 KB Output is correct
87 Correct 901 ms 23716 KB Output is correct
88 Correct 7 ms 768 KB Output is correct
89 Correct 7 ms 768 KB Output is correct
90 Correct 1637 ms 46524 KB Output is correct
91 Correct 1514 ms 44608 KB Output is correct
92 Correct 1326 ms 42736 KB Output is correct
93 Correct 1330 ms 42824 KB Output is correct
94 Correct 45 ms 4728 KB Output is correct
95 Correct 146 ms 10896 KB Output is correct
96 Correct 952 ms 34664 KB Output is correct
97 Correct 866 ms 34488 KB Output is correct
98 Correct 1217 ms 41112 KB Output is correct
99 Correct 1048 ms 41232 KB Output is correct
100 Correct 1408 ms 41872 KB Output is correct
101 Correct 1126 ms 41868 KB Output is correct
102 Correct 1713 ms 42272 KB Output is correct
103 Correct 1392 ms 42312 KB Output is correct
104 Correct 882 ms 31308 KB Output is correct
105 Correct 718 ms 21368 KB Output is correct
106 Correct 808 ms 23972 KB Output is correct
107 Correct 708 ms 26600 KB Output is correct
108 Correct 989 ms 34680 KB Output is correct
109 Correct 821 ms 31096 KB Output is correct
110 Correct 0 ms 384 KB Output is correct
111 Correct 572 ms 24312 KB Output is correct
112 Correct 689 ms 28924 KB Output is correct
113 Correct 909 ms 34168 KB Output is correct
114 Correct 98 ms 5880 KB Output is correct
115 Correct 128 ms 7416 KB Output is correct
116 Correct 145 ms 8312 KB Output is correct
117 Correct 2270 ms 83160 KB Output is correct
118 Correct 2045 ms 78328 KB Output is correct
119 Correct 1935 ms 75260 KB Output is correct
120 Correct 2013 ms 83220 KB Output is correct
121 Correct 1676 ms 83300 KB Output is correct
122 Correct 911 ms 32120 KB Output is correct
123 Correct 768 ms 21540 KB Output is correct
124 Correct 791 ms 23328 KB Output is correct
125 Correct 709 ms 35696 KB Output is correct
126 Correct 916 ms 39720 KB Output is correct
127 Correct 685 ms 33928 KB Output is correct
128 Correct 1665 ms 46384 KB Output is correct
129 Correct 1490 ms 44468 KB Output is correct
130 Correct 1327 ms 42816 KB Output is correct
131 Correct 1345 ms 42708 KB Output is correct
132 Correct 43 ms 4728 KB Output is correct
133 Correct 134 ms 10984 KB Output is correct
134 Correct 911 ms 34604 KB Output is correct
135 Correct 808 ms 34580 KB Output is correct
136 Correct 1216 ms 41100 KB Output is correct
137 Correct 992 ms 41112 KB Output is correct
138 Correct 1421 ms 41876 KB Output is correct
139 Correct 1115 ms 41884 KB Output is correct
140 Correct 1601 ms 42168 KB Output is correct
141 Correct 1440 ms 42256 KB Output is correct
142 Correct 992 ms 31368 KB Output is correct
143 Correct 720 ms 21244 KB Output is correct
144 Correct 836 ms 24244 KB Output is correct
145 Correct 717 ms 26808 KB Output is correct
146 Correct 943 ms 35284 KB Output is correct
147 Correct 728 ms 29976 KB Output is correct
148 Correct 7 ms 1152 KB Output is correct
149 Correct 8 ms 1152 KB Output is correct
150 Correct 10 ms 1152 KB Output is correct
151 Correct 9 ms 1152 KB Output is correct
152 Correct 8 ms 1152 KB Output is correct
153 Correct 11 ms 1152 KB Output is correct
154 Correct 11 ms 1152 KB Output is correct
155 Correct 8 ms 1152 KB Output is correct
156 Correct 8 ms 1024 KB Output is correct
157 Correct 10 ms 1152 KB Output is correct
158 Correct 7 ms 896 KB Output is correct
159 Correct 6 ms 768 KB Output is correct
160 Correct 6 ms 768 KB Output is correct
161 Correct 5 ms 768 KB Output is correct
162 Correct 5 ms 768 KB Output is correct
163 Correct 4 ms 768 KB Output is correct
164 Correct 0 ms 384 KB Output is correct
165 Correct 1 ms 384 KB Output is correct
166 Correct 3 ms 640 KB Output is correct
167 Correct 5 ms 768 KB Output is correct
168 Correct 5 ms 768 KB Output is correct
169 Correct 2 ms 512 KB Output is correct
170 Correct 2 ms 512 KB Output is correct
171 Correct 2 ms 488 KB Output is correct
172 Correct 2360 ms 83124 KB Output is correct
173 Correct 2088 ms 78372 KB Output is correct
174 Correct 1986 ms 75212 KB Output is correct
175 Correct 1979 ms 75364 KB Output is correct
176 Correct 1661 ms 82984 KB Output is correct
177 Correct 2241 ms 83048 KB Output is correct
178 Correct 912 ms 32104 KB Output is correct
179 Correct 819 ms 21676 KB Output is correct
180 Correct 925 ms 23724 KB Output is correct
181 Correct 709 ms 35668 KB Output is correct
182 Correct 867 ms 39736 KB Output is correct
183 Correct 733 ms 35864 KB Output is correct