oj.uz

답안 #851630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
851630 2023-09-20T09:48:45 Z TranGiaHuy1508 Travelling Trader (CCO23_day2problem2) C++17
25 / 25
 456 ms 100364 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

#define int long long

const int inf = 1e15;

int n, K;
vector<int> v, par;
vector<vector<int>> adj;
vector<int> sum_child;
vector<int> max_path;

namespace K2 {
	struct Pair3{
		int path_11, path_00, path_1x;

		bool operator < (const Pair3 &P) const {
			if (path_11 != P.path_11) return (path_11 < P.path_11);
			if (path_00 != P.path_00) return (path_00 < P.path_00);
			return (path_1x < P.path_1x);
		}
	};

	vector<int> dp_00, dp_11, dp_1x, dp_0x;
	vector<int> trace_00, trace_11;
	vector<pair<int, int>> trace_1x;
	vector<int> trace_skip_1x;
	vector<Pair3> trace_0x;
	vector<pair<int, int>> trace_0x_bruh;
	vector<int> case_0x;

	int f_00(int x, int p);
	int f_11(int x, int p);
	int f_0x(int x, int p);
	int f_1x(int x, int p);
	
	int f_00(int x, int p = -1){
		if (dp_00[x] >= 0) return dp_00[x];
		int opt = 0, best = -1;
		for (auto k: adj[x]){
			if (k == p) continue;
			int diff = f_11(k, x) - v[k];
			if (diff > opt){
				opt = diff;
				best = k;
			}
		}
		int ans = sum_child[x] + v[x] + opt;
		trace_00[x] = best;
		dp_00[x] = ans;

		return dp_00[x];
	}

	int f_11(int x, int p = -1){
		if (dp_11[x] >= 0) return dp_11[x];
		int opt = 0, best = -1;
		for (auto k: adj[x]){
			if (k == p) continue;
			int diff = f_00(k, x) - v[k];
			if (diff > opt){
				opt = diff;
				best = k;
			}
		}
		int ans = sum_child[x] + v[x] + opt;
		trace_11[x] = best;
		dp_11[x] = ans;

		return dp_11[x];
	}

	int f_0x(int x, int p = -1){
		if (dp_0x[x] >= 0) return dp_0x[x];
		vector<pair<int, int>> delta_11, delta_00, delta_1x, delta_0x;

		for (auto k: adj[x]){
			if (k == p) continue;
			delta_11.emplace_back(f_11(k, x) - v[k], k);
			delta_00.emplace_back(f_00(k, x) - v[k], k);
			delta_1x.emplace_back(f_1x(k, x) - v[k], k);
			delta_0x.emplace_back(f_0x(k, x) - v[k], k);
		}

		if (delta_00.empty()){
			dp_0x[x] = v[x];
			trace_0x[x] = Pair3{-1, -1, -1};
			return dp_0x[x];
		}

		sort(delta_11.begin(), delta_11.end(), greater<>());
		sort(delta_00.begin(), delta_00.end(), greater<>());
		sort(delta_1x.begin(), delta_1x.end(), greater<>());
		sort(delta_0x.begin(), delta_0x.end(), greater<>());

		long unsigned maxlen = 3;

		delta_11.resize(min(delta_11.size(), maxlen));
		delta_00.resize(min(delta_00.size(), maxlen));
		delta_1x.resize(min(delta_1x.size(), maxlen));
		delta_0x.resize(min(delta_1x.size(), maxlen));

		delta_11.emplace_back(0, -2);
		delta_00.emplace_back(0, -3);
		delta_1x.emplace_back(0, -4);
		delta_0x.emplace_back(0, -5);
		
		pair<int, Pair3> final_opt(0, Pair3{-1, -1, -1});
		for (auto p11: delta_11){
			for (auto p00: delta_00){
				if (p11.second == p00.second) continue;
				for (auto p1x: delta_1x){
					if (p11.second == p1x.second) continue;
					if (p00.second == p1x.second) continue;

					pair<int, Pair3> crr_opt = {
						p11.first + p00.first + p1x.first,
						Pair3{
							p11.second,
							p00.second,
							p1x.second
						}
					};

					final_opt = max(final_opt, crr_opt);
				}
			}
		}

		int ans1 = sum_child[x] + v[x] + final_opt.first;

		pair<int, pair<int, int>> bruh_opt = {0, {-1, -1}};
		for (auto p11: delta_11){
			for (auto p0x: delta_0x){
				if (p11.second == p0x.second) continue;

				pair<int, pair<int, int>> crr_opt = {
					p11.first + p0x.first,
					{
						p11.second, p0x.second
					}
				};

				bruh_opt = max(bruh_opt, crr_opt);
			}
		}

		int ans2 = sum_child[x] + v[x] + bruh_opt.first;

		if (ans1 >= ans2){
			trace_0x[x] = final_opt.second;
			dp_0x[x] = ans1;
		}
		else{
			trace_0x_bruh[x] = bruh_opt.second;
			dp_0x[x] = ans2;
			case_0x[x] = 1;
		}

		return dp_0x[x];
	}

	int f_1x(int x, int p = -1){
		if (dp_1x[x] >= 0) return dp_1x[x];
		vector<pair<int, int>> delta_00, delta_1x;
		for (auto k: adj[x]){
			if (k == p) continue;
			delta_00.emplace_back(f_00(k, x) - v[k], k);
			delta_1x.emplace_back(f_1x(k, x) - v[k], k);
		}

		if (delta_00.empty()){
			dp_1x[x] = v[x];
			trace_1x[x] = {-1, -1};
			return dp_1x[x];
		}

		sort(delta_00.begin(), delta_00.end(), greater<>());
		sort(delta_1x.begin(), delta_1x.end(), greater<>());

		long unsigned maxlen = 2;

		delta_00.resize(min(delta_00.size(), maxlen));
		delta_1x.resize(min(delta_1x.size(), maxlen));

		delta_00.emplace_back(0, -2);
		delta_1x.emplace_back(0, -3);

		pair<int, pair<int, int>> final_opt(0, {-1, -1});
		for (auto p00: delta_00){
			for (auto p1x: delta_1x){
				if (p00.second == p1x.second) continue;

				pair<int, pair<int, int>> crr_opt = {
					p00.first + p1x.first,
					{
						p1x.second, p00.second
					}
				};

				final_opt = max(final_opt, crr_opt);
			}
		}

		int ans = sum_child[x] + v[x] + final_opt.first;
		trace_1x[x] = final_opt.second;

		for (auto k: adj[x]){
			if (k == p) continue;
			int newval = v[x] + f_0x(k, x);
			if (newval > ans){
				trace_skip_1x[x] = k;
				ans = newval;
			}
		}

		dp_1x[x] = ans;

		return dp_1x[x];
	}

	vector<int> trace;

	void tracing_00(int x, int p);
	void tracing_11(int x, int p);
	void tracing_0x(int x, int p);
	void tracing_1x(int x, int p);

	void tracing_00(int x, int p = -1){
		for (auto k: adj[x]){
			if (k == p) continue;
			if (k == trace_00[x]) continue;
			trace.push_back(k);
		}
		if (trace_00[x] >= 0){
			tracing_11(trace_00[x], x);
		}
		trace.push_back(x);
	}

	void tracing_11(int x, int p = -1){
		trace.push_back(x);
		if (trace_11[x] >= 0){
			tracing_00(trace_11[x], x);
		}
		for (auto k: adj[x]){
			if (k == p) continue;
			if (k == trace_11[x]) continue;
			trace.push_back(k);
		}
	}
	
	void tracing_0x(int x, int p = -1){
		if (case_0x[x] == 0){
			if (trace_0x[x].path_11 >= 0){
				tracing_11(trace_0x[x].path_11, x);
			}

			trace.push_back(x);

			if (trace_0x[x].path_00 >= 0){
				tracing_00(trace_0x[x].path_00, x);
			}

			for (auto k: adj[x]){
				if (k == p) continue;
				if (k == trace_0x[x].path_11) continue;
				if (k == trace_0x[x].path_00) continue;
				if (k == trace_0x[x].path_1x) continue;
				trace.push_back(k);
			}

			if (trace_0x[x].path_1x >= 0){
				tracing_1x(trace_0x[x].path_1x, x);
			}
		}
		else{
			for (auto k: adj[x]){
				if (k == p) continue;
				if (k == trace_0x_bruh[x].first) continue;
				if (k == trace_0x_bruh[x].second) continue;
				trace.push_back(k);
			}

			if (trace_0x_bruh[x].first >= 0){
				tracing_11(trace_0x_bruh[x].first, x);
			}
			trace.push_back(x);
			if (trace_0x_bruh[x].second >= 0){
				tracing_0x(trace_0x_bruh[x].second, x);
			}
		}
	}

	void tracing_1x(int x, int p = -1){
		trace.push_back(x);

		if (trace_skip_1x[x] >= 0){
			tracing_0x(trace_skip_1x[x], x);
			return;
		}

		if (trace_1x[x].second >= 0){
			tracing_00(trace_1x[x].second, x);
		}
		for (auto k: adj[x]){
			if (k == p) continue;
			if (k == trace_1x[x].first) continue;
			if (k == trace_1x[x].second) continue;
			trace.push_back(k);
		}
		if (trace_1x[x].first >= 0){
			tracing_1x(trace_1x[x].first, x);
		}
	}

	void solve(){
		dp_00.assign(n, -inf);
		dp_11.assign(n, -inf);
		dp_0x.assign(n, -inf);
		dp_1x.assign(n, -inf);

		trace_00.assign(n, -1);
		trace_11.assign(n, -1);
		trace_1x.assign(n, {-1, -1});
		trace_0x.assign(n, Pair3{-1, -1, -1});
		trace_skip_1x.assign(n, -1);
		trace_0x_bruh.assign(n, {-1, -1});
		case_0x.assign(n, 0);

		cout << f_1x(0) << "\n";
		tracing_1x(0);
		cout << trace.size() << "\n";
		for (int i = 0; i < trace.size(); i++){
			cout << trace[i] + 1 << " \n"[i == trace.size() - 1];
		}
	}
}

void dfs(int x, int p = -1){
	par[x] = p;
	for (auto k: adj[x]){
		if (k == p) continue;
		dfs(k, x);
		sum_child[x] += v[k];
	}
}

void dfs_K1(int x, int p = -1){
	for (auto k: adj[x]){
		if (k == p) continue;
		dfs_K1(k, x);
		max_path[x] = max(max_path[x], max_path[k]);
	}
	max_path[x] += v[x];
}

void solve_K1(){
	dfs_K1(0);

	vector<int> trace;
	trace.push_back(0);
	int crr = 0;

	while (true){
		int opt = -1, nxt = -1;
		for (auto k: adj[crr]){
			if (k == par[crr]) continue;
			if (max_path[k] > opt){
				opt = max_path[k];
				nxt = k;
			}
		}
		if (opt < 0) break;
		trace.push_back(nxt);
		crr = nxt;
	}

	cout << max_path[0] << "\n";
	cout << trace.size() << "\n";
	for (int i = 0; i < trace.size(); i++){
		cout << trace[i] + 1 << " \n"[i == trace.size() - 1];
	}
}

vector<int> trace;
void dfs_K3_2(int x, int p);

void dfs_K3_1(int x, int p = -1){
	trace.push_back(x);
	for (auto k: adj[x]){
		if (k == p) continue;
		dfs_K3_2(k, x);
	}
}

void dfs_K3_2(int x, int p = -1){
	for (auto k: adj[x]){
		if (k == p) continue;
		dfs_K3_1(k, x);
	}
	trace.push_back(x);
}

void solve_K3(){
	cout << accumulate(v.begin(), v.end(), 0LL) << "\n";
	cout << n << "\n";
	dfs_K3_1(0);
	for (int i = 0; i < n; i++){
		cout << trace[i] + 1 << " \n"[i == n-1];
	}
}

void main_program(){
	cin >> n >> K;

	adj.resize(n);
	v.resize(n);
	par.resize(n);
	sum_child.resize(n);
	max_path.resize(n);

	for (int i = 0; i < n-1; i++){
		int x, y; cin >> x >> y;
		x--; y--;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	for (int i = 0; i < n; i++) cin >> v[i];

	dfs(0);
	if (K == 1){
		solve_K1();
	}
	else if (K == 2){
		K2::solve();
	}
	else{
		solve_K3();
	}
}

Compilation message

Main.cpp: In function 'void K2::solve()':
Main.cpp:342:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  342 |   for (int i = 0; i < trace.size(); i++){
      |                   ~~^~~~~~~~~~~~~~
Main.cpp:343:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  343 |    cout << trace[i] + 1 << " \n"[i == trace.size() - 1];
      |                                  ~~^~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve_K1()':
Main.cpp:389:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  389 |  for (int i = 0; i < trace.size(); i++){
      |                  ~~^~~~~~~~~~~~~~
Main.cpp:390:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  390 |   cout << trace[i] + 1 << " \n"[i == trace.size() - 1];
      |                                 ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 104 ms 18772 KB Output is correct
4 Correct 96 ms 18768 KB Output is correct
5 Correct 168 ms 18728 KB Output is correct
6 Correct 89 ms 19536 KB Output is correct
7 Correct 70 ms 19408 KB Output is correct
8 Correct 105 ms 18460 KB Output is correct
9 Correct 191 ms 32960 KB Output is correct
10 Correct 157 ms 27848 KB Output is correct
11 Correct 56 ms 19024 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 504 KB Output is correct
28 Correct 1 ms 344 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 504 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 2 ms 856 KB Output is correct
32 Correct 3 ms 856 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 3 ms 856 KB Output is correct
36 Correct 3 ms 856 KB Output is correct
37 Correct 2 ms 936 KB Output is correct
38 Correct 2 ms 856 KB Output is correct
39 Correct 2 ms 856 KB Output is correct
40 Correct 2 ms 856 KB Output is correct
41 Correct 2 ms 860 KB Output is correct
42 Correct 4 ms 1528 KB Output is correct
43 Correct 2 ms 1112 KB Output is correct
44 Correct 2 ms 1056 KB Output is correct
45 Correct 2 ms 860 KB Output is correct
46 Correct 2 ms 856 KB Output is correct
47 Correct 2 ms 856 KB Output is correct
48 Correct 2 ms 860 KB Output is correct
49 Correct 2 ms 856 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 344 KB Output is correct
20 Correct 1 ms 600 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 1 ms 504 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 856 KB Output is correct
31 Correct 2 ms 856 KB Output is correct
32 Correct 3 ms 856 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 2 ms 856 KB Output is correct
35 Correct 3 ms 856 KB Output is correct
36 Correct 3 ms 856 KB Output is correct
37 Correct 2 ms 936 KB Output is correct
38 Correct 2 ms 856 KB Output is correct
39 Correct 2 ms 856 KB Output is correct
40 Correct 2 ms 856 KB Output is correct
41 Correct 2 ms 860 KB Output is correct
42 Correct 4 ms 1528 KB Output is correct
43 Correct 2 ms 1112 KB Output is correct
44 Correct 2 ms 1056 KB Output is correct
45 Correct 2 ms 860 KB Output is correct
46 Correct 2 ms 856 KB Output is correct
47 Correct 2 ms 856 KB Output is correct
48 Correct 2 ms 860 KB Output is correct
49 Correct 2 ms 856 KB Output is correct
50 Correct 317 ms 46884 KB Output is correct
51 Correct 298 ms 46672 KB Output is correct
52 Correct 283 ms 46872 KB Output is correct
53 Correct 271 ms 46924 KB Output is correct
54 Correct 266 ms 46884 KB Output is correct
55 Correct 345 ms 46792 KB Output is correct
56 Correct 224 ms 47592 KB Output is correct
57 Correct 310 ms 46988 KB Output is correct
58 Correct 226 ms 47928 KB Output is correct
59 Correct 310 ms 46928 KB Output is correct
60 Correct 216 ms 47952 KB Output is correct
61 Correct 142 ms 57060 KB Output is correct
62 Correct 240 ms 49148 KB Output is correct
63 Correct 227 ms 49048 KB Output is correct
64 Correct 180 ms 47740 KB Output is correct
65 Correct 456 ms 100364 KB Output is correct
66 Correct 404 ms 77516 KB Output is correct
67 Correct 337 ms 66128 KB Output is correct
68 Correct 337 ms 64588 KB Output is correct
69 Correct 362 ms 56648 KB Output is correct
70 Correct 329 ms 54720 KB Output is correct
71 Correct 163 ms 46928 KB Output is correct
72 Correct 123 ms 46480 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 2 ms 600 KB Output is correct
5 Correct 1 ms 760 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 600 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 1 ms 600 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 1 ms 600 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 600 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 128 ms 21824 KB Output is correct
25 Correct 116 ms 21900 KB Output is correct
26 Correct 104 ms 21988 KB Output is correct
27 Correct 133 ms 21668 KB Output is correct
28 Correct 110 ms 21768 KB Output is correct
29 Correct 108 ms 21696 KB Output is correct
30 Correct 94 ms 22464 KB Output is correct
31 Correct 139 ms 21904 KB Output is correct
32 Correct 112 ms 22748 KB Output is correct
33 Correct 104 ms 21704 KB Output is correct
34 Correct 95 ms 22588 KB Output is correct
35 Correct 71 ms 22208 KB Output is correct
36 Correct 87 ms 21312 KB Output is correct
37 Correct 184 ms 21784 KB Output is correct
38 Correct 95 ms 22312 KB Output is correct
39 Correct 192 ms 33060 KB Output is correct
40 Correct 179 ms 29208 KB Output is correct
41 Correct 140 ms 26584 KB Output is correct
42 Correct 142 ms 26084 KB Output is correct
43 Correct 161 ms 24464 KB Output is correct
44 Correct 114 ms 23232 KB Output is correct
45 Correct 70 ms 22216 KB Output is correct
46 Correct 67 ms 21700 KB Output is correct