답안 #789616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
789616	2023-07-21T14:53:34 Z	hugo_pm	Two Currencies (JOI23_currencies)	C++17	100 / 100	1829 ms	283932 KB

currencies

// Begin hl/core.hpp
#pragma once
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using v32 = vector<int>;
using v64 = vector<ll>;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
const int m197 = 1000000007;
const int m998 = 998244353;

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i, a, b) for(int i = (a); i < (b); i++)

template<typename T>
void chmax(T &x, const T &v) { if (x < v) x = v; }
template<typename T>
void chmin(T &x, const T &v) { if (x > v) x = v; }
template<typename T>
int len(const T &x) { return (int)(x.size()); }

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) {
	cout << ' ' << H;
	dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type
operator<<(Ostream& os,  const Cont& v){
	os << "[";
	for (auto &x : v) os << x << ", ";
	return os << "]";
}

template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p) {
	return os << "{" << p.first << ", " << p.second << "}";
}

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename... Args>
		Vec(int n, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {}
};

template<typename T>
struct Vec<1, T> : public vector<T> {
	Vec(int n, const T& val = T()) : vector<T>(n, val) {}
};

template<class Fun>
class letrec_result {
	Fun fun_;
public:
	template<class T>
		explicit letrec_result(T &&fun): fun_(std::forward<T>(fun)) {}

	template<class ...Args>
		decltype(auto) operator()(Args &&...args) {
			return fun_(ref(*this), std::forward<Args>(args)...);
		}
};

template<class Fun>
decltype(auto) letrec(Fun &&fun) {
	return letrec_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

ll nxt() { ll x; cin >> x; return x; }
template<typename T>
vector<T> read_vector(int n) {
	vector<T> v(n);
	for (T &x : v) cin >> x;
	return v;
}
vector<int> rv32(int n) { return read_vector<int>(n); }
vector<ll> rv64(int n) { return read_vector<ll>(n); }

template<typename T>
void print_vector(vector<T> data, bool print_size, bool new_line) {
	int n = data.size();
	if (print_size) cout << n << '\n';
	for (int i = 0; i < n; ++i) cout << data[i] << " \n"[i+1 == n || new_line];
}

void fastio() {
	ios::sync_with_stdio(false), cin.tie(0);
}

vector<int> az_to_int(string s) {
	vector<int> ret(s.size());
	rep(i, 0, (int)s.size()) ret[i] = s[i] - 'a';
	return ret;
}
// End hl/core.hpp
// Begin hl/data/usual.hpp
#pragma once
// Begin hl/data/segtree.hpp
#pragma once
#include <vector>

template<class node, node (*op)(node, node), node (*e)()>
class segtree {
public:
	segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());

		for (int i = 0; i < _n; ++i) {
			data[size+i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update(i);
		}
	}

	segtree(int t = 0, node x = e()) : segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		return data[size+pos];
	}

	void set(int pos, node val) {
		pos += size;
		data[pos] = val;
		for (int i = 1; i <= log; ++i) {
			update(pos >> i);
		}
	}

	void refresh(int pos, node proposal) {
		set(pos, op(data[size+pos], proposal));
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e(); 

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1, right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

private:
	int _n, log, size;
	std::vector<node> data;

	void update(int k) {
		data[k] = op(data[k<<1], data[k<<1|1]);
	}
};
// End hl/data/segtree.hpp
// Begin hl/data/lazy_segtree.hpp
#pragma once
#include <vector>
#include <cassert>

template<class node,
node (*op)(node, node),
node (*e)(),
class fun,
node (*eval)(fun, node),
fun (*composition)(fun, fun),
fun (*id)()>
class lazy_segtree {
public:
	lazy_segtree(std::vector<node> v) : _n(v.size()), log(0) {
		while ((1 << log) < _n) {
			++log;
		}

		size = (1 << log);
		data.assign(2*size, e());
		lazy.assign(size, id());

		for (int i = 0; i < _n; ++i) {
			data[size + i] = v[i];
		}

		for (int i = size-1; i >= 1; --i) {
			update_one(i);
		}
	}

	lazy_segtree(int t = 0, node x = e()) : lazy_segtree(std::vector<node>(t, x)) { }

	node get(int pos) {
		int leaf = pos + size;
		push_anc(leaf);
		return data[leaf];
	}

	void set(int pos, node val) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = val;
		update_anc(leaf);
	}

	node query_semi_open(int left, int right) {
		left += size;
		right += size;
		node res_left = e(), res_right = e();

		push_anc(left, left);
		push_anc(right, right);

		while (left < right) {
			if (left & 1) {
				res_left = op(res_left, data[left++]);
			}
			if (right & 1) {
				res_right = op(data[--right], res_right);
			}
			left >>= 1;
			right >>= 1;	
		}

		return op(res_left, res_right);
	}

	node query_all() {
		return data[1];
	}

	void apply_one(int pos, fun fct) {
		int leaf = pos + size;
		push_anc(leaf);
		data[leaf] = eval(fct, data[leaf]);
		update_anc(leaf);
	}

	void apply_semi_open(int left, int right, fun fct) {
		left += size;
		right += size;

		if (left == right) {
			return;
		}

		push_anc(left, left);
		push_anc(right - 1, right);

		int old_left = left, old_right = right;
		while (left < right) {
			if (left & 1) {
				all_apply(left++, fct);
			}
			if (right & 1) {
				all_apply(--right, fct);
			}
			left >>= 1;
			right >>= 1;
		}

		left = old_left, right = old_right;
		update_anc(left, left);
		update_anc(right - 1, right);
	}

private:
	int _n, log, size;
	std::vector<node> data;
	std::vector<fun> lazy;

	void update_one(int k) {
		data[k] = op(data[k << 1], data[k << 1 | 1]);
	}

	void update_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = s; i <= log; ++i) {
			update_one(leaf >> i);
		}
	}

	void all_apply(int k, fun fct) {
		data[k] = eval(fct, data[k]);
		if (k < size) {
			lazy[k] = composition(fct, lazy[k]);
		}
	}

	void push_one(int k) {
		all_apply(k << 1, lazy[k]);
		all_apply(k << 1 | 1, lazy[k]);
		lazy[k] = id();
	}

	void push_anc(int leaf, int dev = 1) {
		int s = 1 + __builtin_ctz(dev);
		for (int i = log; i >= s; --i) {
			push_one(leaf >> i);
		}
	}
};
// End hl/data/lazy_segtree.hpp
#include <optional>
using ll = long long;

template<typename T, const T BIG_>
struct numeric_segtree {
	static constexpr T BIG = BIG_;
	static T fct_sum(T a, T b) { return a + b; }
	static T e_sum() { return 0; }

	static T fct_min(T a, T b) { return (a < b ? a : b); }
	static T e_min() { return BIG; }

	static T fct_max(T a, T b) { return (a > b ? a : b); }
	static T e_max() { return -BIG; }

	using segtree_min = segtree<T, fct_min, e_min>;
	using segtree_max = segtree<T, fct_max, e_max>;
	using segtree_sum = segtree<T, fct_sum, e_sum>;

	using lazy_min_add = lazy_segtree<T, fct_min, e_min, T, fct_sum, fct_sum, e_sum>;
	using lazy_max_add = lazy_segtree<T, fct_max, e_max, T, fct_sum, fct_sum, e_sum>;
	using lazy_sum_add = lazy_segtree<T, fct_sum, e_sum, T, fct_sum, fct_sum, e_sum>;

	using set_struct = std::optional<T>;
	static set_struct comp_set(set_struct f1, set_struct f2) {
		return (f1 ? f1 : f2);
	}
	static T eval_set(set_struct fct, T val) {
		return (fct ? *fct : val);
	}
	static set_struct e_set() {
		return std::nullopt;
	}

	using lazy_min_set = lazy_segtree<T, fct_min, e_min, set_struct, eval_set, comp_set, e_set>;
	using lazy_max_set = lazy_segtree<T, fct_max, e_max, set_struct, eval_set, comp_set, e_set>;
	using lazy_sum_set = lazy_segtree<T, fct_sum, e_sum, set_struct, eval_set, comp_set, e_set>;
};

using usual32 = numeric_segtree<int, (int)1e9>;
using usual64 = numeric_segtree<long long, (ll)3e18>;

// End hl/data/usual.hpp
#define int long long

using pii = pair<int, int>;
using vi = vector<int>;
const int INF = 3e18;
pii opmin(pii a, pii b) {
    return min(a, b);
}
pii e_min() { return {INF, -1}; }
using SegSum = usual64::segtree_sum;
using SegMin = segtree<pii, opmin, e_min>;

struct PathSumEdge {
	vector<vi> adj;
	int N;
	int ordCnt = 0;
	vector<pii> begEnd;
	vector<pii> passages;
	vector<int> firstPass;
	vector<int> depth;
	SegMin lca_tree;
	SegSum sum_tree;

	void dfs(int node, int anc) {
		begEnd[node].first = ordCnt++;
		firstPass[node]= passages.size();
		passages.emplace_back(depth[node], node);
		for(auto voisin : adj[node]) if (voisin != anc) {
			depth[voisin] = depth[node]+1;
			dfs(voisin, node);
			passages.emplace_back(depth[node], node);
		}
		begEnd[node].second = ordCnt++;
	}

	void resetSum() {
		sum_tree = SegSum(2*N, 0);
	}

	PathSumEdge(int _N, vector<vi> _adj) :
	adj(_adj), N(_N), begEnd(_N), firstPass(_N), depth(_N) {
		assert(N == (int)adj.size());
		dfs(0, -1);
		lca_tree = SegMin(passages);
		resetSum();
	}

	void edgeAdd(int u, int v, int delta) {
		if (depth[u] > depth[v]) swap(u, v);
		// u parent, v child
		sum_tree.refresh(begEnd[v].first, delta);
		sum_tree.refresh(begEnd[v].second, -delta);
	}

	int edgePathSum(int u, int v) {
		if(firstPass[u] > firstPass[v]){
			swap(u, v);
		}
		int lca = lca_tree.query_semi_open(firstPass[u], firstPass[v]+1).second;
		int res = 0;
		// (lca, u/v]
		for (int x : {u, v})
			res += sum_tree.query_semi_open(begEnd[lca].first+1, begEnd[x].first+1);
		return res;
	}
};

struct Query {
	int id;
	// gold = initial - tout
	int S, T, gold, silver;
	// [lo, hi] : nombre de silverables
	int lo, hi;
	int mid() { return lo + (hi-lo+1)/2; }
};
signed main() {
	fastio();
	int nbNode = nxt(), nbChk = nxt(), nbReq = nxt();
	vector<vi> adj(nbNode);
	vector<pii> edges;
	rep(iEdge, 0, nbNode-1) {
		int u = nxt()-1, v = nxt()-1;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.emplace_back(u, v);
	}
	PathSumEdge ps(nbNode, adj);
	vector<pair<int, pii>> checkpoints;
	rep(iChk, 0, nbChk) {
		int iEdge = nxt()-1, bonus = nxt();
		checkpoints.emplace_back(bonus, edges[iEdge]);
		// calcul nombre de chk
		ps.edgeAdd(edges[iEdge].first, edges[iEdge].second, 1);
	}
	sort(all(checkpoints));
	vector<vector<Query>> done(nbChk+1);
	int nbDone = 0;
	vector<vector<Query>> _empty(nbChk+1);
	auto todo = _empty;
	auto push = [&] (Query &r) {
		if (r.lo == r.hi) {
			done[r.mid()].push_back(r); ++nbDone;
		} else {
			todo[r.mid()].push_back(r);
		}
	};
	rep(iReq, 0, nbReq) {
		Query r;
		r.id = iReq;
		cin >> r.S >> r.T >> r.gold >> r.silver;
		--r.S; --r.T;
		r.gold -= ps.edgePathSum(r.S, r.T);
		r.lo = 0, r.hi = nbChk;
		push(r);
	}
	vector<vector<Query>> old;
	while (nbDone < nbReq) {
		old = todo;
		todo = _empty;
		ps.resetSum();
		rep(taken, 1, nbChk+1) {
			auto [bonus, edge] = checkpoints[taken-1];
			auto [u, v] = edge;
			ps.edgeAdd(u, v, bonus);
			for (Query r : old[taken]) {
				if (r.silver < ps.edgePathSum(r.S, r.T)) {
					r.hi = taken-1;
				} else {
					r.lo = taken;
				}
				push(r);
			}
		}
	}
	vector<int> answers(nbReq);
	ps.resetSum();
	rep(taken, 0, nbChk+1) {
		for (Query r : done[taken]) {
			answers[r.id] = max(-1LL, r.gold + ps.edgePathSum(r.S, r.T));
		}
		if (taken < nbChk) {
			auto [u, v] = checkpoints[taken].second;
			ps.edgeAdd(u, v, 1);
		}
	}
	rep(iReq, 0, nbReq) {
		cout << answers[iReq] << '\n';
	}
}

Compilation message

currencies.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~
currencies.cpp:109:9: warning: #pragma once in main file
  109 | #pragma once
      |         ^~~~
currencies.cpp:111:9: warning: #pragma once in main file
  111 | #pragma once
      |         ^~~~
currencies.cpp:184:9: warning: #pragma once in main file
  184 | #pragma once
      |         ^~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	2920 KB	Output is correct
6	Correct	11 ms	4044 KB	Output is correct
7	Correct	10 ms	3668 KB	Output is correct
8	Correct	13 ms	4308 KB	Output is correct
9	Correct	12 ms	4180 KB	Output is correct
10	Correct	13 ms	4204 KB	Output is correct
11	Correct	12 ms	4180 KB	Output is correct
12	Correct	12 ms	4308 KB	Output is correct
13	Correct	10 ms	4296 KB	Output is correct
14	Correct	11 ms	4228 KB	Output is correct
15	Correct	11 ms	4236 KB	Output is correct
16	Correct	11 ms	4264 KB	Output is correct
17	Correct	13 ms	4280 KB	Output is correct
18	Correct	11 ms	4232 KB	Output is correct
19	Correct	11 ms	4180 KB	Output is correct
20	Correct	11 ms	4180 KB	Output is correct
21	Correct	11 ms	4180 KB	Output is correct
22	Correct	10 ms	4180 KB	Output is correct
23	Correct	10 ms	4292 KB	Output is correct
24	Correct	10 ms	4308 KB	Output is correct
25	Correct	10 ms	4180 KB	Output is correct
26	Correct	8 ms	4172 KB	Output is correct
27	Correct	6 ms	4260 KB	Output is correct
28	Correct	7 ms	4308 KB	Output is correct
29	Correct	6 ms	3916 KB	Output is correct
30	Correct	12 ms	4148 KB	Output is correct
31	Correct	12 ms	4276 KB	Output is correct
32	Correct	12 ms	4180 KB	Output is correct
33	Correct	10 ms	4376 KB	Output is correct
34	Correct	10 ms	4300 KB	Output is correct
35	Correct	10 ms	4300 KB	Output is correct

Subtask #2

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	12 ms	4220 KB	Output is correct
3	Correct	15 ms	4168 KB	Output is correct
4	Correct	12 ms	4200 KB	Output is correct
5	Correct	1044 ms	187560 KB	Output is correct
6	Correct	1232 ms	255480 KB	Output is correct
7	Correct	1155 ms	240024 KB	Output is correct
8	Correct	907 ms	185012 KB	Output is correct
9	Correct	935 ms	178376 KB	Output is correct
10	Correct	1484 ms	273476 KB	Output is correct
11	Correct	1473 ms	271624 KB	Output is correct
12	Correct	1455 ms	272308 KB	Output is correct
13	Correct	1466 ms	271896 KB	Output is correct
14	Correct	1486 ms	272052 KB	Output is correct
15	Correct	1169 ms	275776 KB	Output is correct
16	Correct	1116 ms	276028 KB	Output is correct
17	Correct	1143 ms	274868 KB	Output is correct
18	Correct	1416 ms	270888 KB	Output is correct
19	Correct	1431 ms	270904 KB	Output is correct
20	Correct	1415 ms	271392 KB	Output is correct
21	Correct	1189 ms	275660 KB	Output is correct
22	Correct	1160 ms	275020 KB	Output is correct
23	Correct	1200 ms	275700 KB	Output is correct
24	Correct	1210 ms	275016 KB	Output is correct
25	Correct	1264 ms	265572 KB	Output is correct
26	Correct	1149 ms	264308 KB	Output is correct
27	Correct	1145 ms	266936 KB	Output is correct
28	Correct	585 ms	283932 KB	Output is correct
29	Correct	586 ms	273768 KB	Output is correct
30	Correct	712 ms	263376 KB	Output is correct
31	Correct	702 ms	257336 KB	Output is correct

Subtask #3

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	10 ms	4316 KB	Output is correct
3	Correct	10 ms	4364 KB	Output is correct
4	Correct	10 ms	4296 KB	Output is correct
5	Correct	726 ms	187520 KB	Output is correct
6	Correct	730 ms	192984 KB	Output is correct
7	Correct	861 ms	220564 KB	Output is correct
8	Correct	1153 ms	275548 KB	Output is correct
9	Correct	1109 ms	274040 KB	Output is correct
10	Correct	1415 ms	274888 KB	Output is correct
11	Correct	1177 ms	276824 KB	Output is correct
12	Correct	1135 ms	275204 KB	Output is correct
13	Correct	1039 ms	276384 KB	Output is correct
14	Correct	674 ms	277500 KB	Output is correct
15	Correct	633 ms	279988 KB	Output is correct
16	Correct	792 ms	278272 KB	Output is correct
17	Correct	825 ms	278032 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	320 KB	Output is correct
3	Correct	0 ms	320 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	8 ms	2920 KB	Output is correct
6	Correct	11 ms	4044 KB	Output is correct
7	Correct	10 ms	3668 KB	Output is correct
8	Correct	13 ms	4308 KB	Output is correct
9	Correct	12 ms	4180 KB	Output is correct
10	Correct	13 ms	4204 KB	Output is correct
11	Correct	12 ms	4180 KB	Output is correct
12	Correct	12 ms	4308 KB	Output is correct
13	Correct	10 ms	4296 KB	Output is correct
14	Correct	11 ms	4228 KB	Output is correct
15	Correct	11 ms	4236 KB	Output is correct
16	Correct	11 ms	4264 KB	Output is correct
17	Correct	13 ms	4280 KB	Output is correct
18	Correct	11 ms	4232 KB	Output is correct
19	Correct	11 ms	4180 KB	Output is correct
20	Correct	11 ms	4180 KB	Output is correct
21	Correct	11 ms	4180 KB	Output is correct
22	Correct	10 ms	4180 KB	Output is correct
23	Correct	10 ms	4292 KB	Output is correct
24	Correct	10 ms	4308 KB	Output is correct
25	Correct	10 ms	4180 KB	Output is correct
26	Correct	8 ms	4172 KB	Output is correct
27	Correct	6 ms	4260 KB	Output is correct
28	Correct	7 ms	4308 KB	Output is correct
29	Correct	6 ms	3916 KB	Output is correct
30	Correct	12 ms	4148 KB	Output is correct
31	Correct	12 ms	4276 KB	Output is correct
32	Correct	12 ms	4180 KB	Output is correct
33	Correct	10 ms	4376 KB	Output is correct
34	Correct	10 ms	4300 KB	Output is correct
35	Correct	10 ms	4300 KB	Output is correct
36	Correct	1 ms	324 KB	Output is correct
37	Correct	12 ms	4220 KB	Output is correct
38	Correct	15 ms	4168 KB	Output is correct
39	Correct	12 ms	4200 KB	Output is correct
40	Correct	1044 ms	187560 KB	Output is correct
41	Correct	1232 ms	255480 KB	Output is correct
42	Correct	1155 ms	240024 KB	Output is correct
43	Correct	907 ms	185012 KB	Output is correct
44	Correct	935 ms	178376 KB	Output is correct
45	Correct	1484 ms	273476 KB	Output is correct
46	Correct	1473 ms	271624 KB	Output is correct
47	Correct	1455 ms	272308 KB	Output is correct
48	Correct	1466 ms	271896 KB	Output is correct
49	Correct	1486 ms	272052 KB	Output is correct
50	Correct	1169 ms	275776 KB	Output is correct
51	Correct	1116 ms	276028 KB	Output is correct
52	Correct	1143 ms	274868 KB	Output is correct
53	Correct	1416 ms	270888 KB	Output is correct
54	Correct	1431 ms	270904 KB	Output is correct
55	Correct	1415 ms	271392 KB	Output is correct
56	Correct	1189 ms	275660 KB	Output is correct
57	Correct	1160 ms	275020 KB	Output is correct
58	Correct	1200 ms	275700 KB	Output is correct
59	Correct	1210 ms	275016 KB	Output is correct
60	Correct	1264 ms	265572 KB	Output is correct
61	Correct	1149 ms	264308 KB	Output is correct
62	Correct	1145 ms	266936 KB	Output is correct
63	Correct	585 ms	283932 KB	Output is correct
64	Correct	586 ms	273768 KB	Output is correct
65	Correct	712 ms	263376 KB	Output is correct
66	Correct	702 ms	257336 KB	Output is correct
67	Correct	1 ms	324 KB	Output is correct
68	Correct	10 ms	4316 KB	Output is correct
69	Correct	10 ms	4364 KB	Output is correct
70	Correct	10 ms	4296 KB	Output is correct
71	Correct	726 ms	187520 KB	Output is correct
72	Correct	730 ms	192984 KB	Output is correct
73	Correct	861 ms	220564 KB	Output is correct
74	Correct	1153 ms	275548 KB	Output is correct
75	Correct	1109 ms	274040 KB	Output is correct
76	Correct	1415 ms	274888 KB	Output is correct
77	Correct	1177 ms	276824 KB	Output is correct
78	Correct	1135 ms	275204 KB	Output is correct
79	Correct	1039 ms	276384 KB	Output is correct
80	Correct	674 ms	277500 KB	Output is correct
81	Correct	633 ms	279988 KB	Output is correct
82	Correct	792 ms	278272 KB	Output is correct
83	Correct	825 ms	278032 KB	Output is correct
84	Correct	1248 ms	187376 KB	Output is correct
85	Correct	1060 ms	196420 KB	Output is correct
86	Correct	972 ms	190896 KB	Output is correct
87	Correct	1829 ms	272640 KB	Output is correct
88	Correct	1607 ms	271424 KB	Output is correct
89	Correct	1641 ms	271552 KB	Output is correct
90	Correct	1624 ms	271208 KB	Output is correct
91	Correct	1676 ms	271784 KB	Output is correct
92	Correct	1325 ms	271680 KB	Output is correct
93	Correct	1288 ms	272484 KB	Output is correct
94	Correct	1587 ms	269520 KB	Output is correct
95	Correct	1573 ms	269188 KB	Output is correct
96	Correct	1578 ms	269056 KB	Output is correct
97	Correct	1575 ms	269032 KB	Output is correct
98	Correct	1392 ms	272664 KB	Output is correct
99	Correct	1423 ms	270936 KB	Output is correct
100	Correct	1413 ms	272500 KB	Output is correct
101	Correct	1418 ms	273016 KB	Output is correct
102	Correct	1250 ms	270768 KB	Output is correct
103	Correct	1259 ms	271004 KB	Output is correct
104	Correct	1320 ms	270320 KB	Output is correct
105	Correct	650 ms	257316 KB	Output is correct
106	Correct	651 ms	276020 KB	Output is correct
107	Correct	770 ms	255180 KB	Output is correct
108	Correct	756 ms	256608 KB	Output is correct