oj.uz

Submission #842465

# Submission time Handle Problem Language Result Execution time Memory
842465 2023-09-02T23:15:23 Z Benq Overtaking (IOI23_overtaking) C++17
100 / 100
 1895 ms 101796 KB 
#include "overtaking.h"

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string;      // yay python!

// pairs
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
#define mp make_pair
#define f first
#define s second

#define tcT template <class T
#define tcTU tcT, class U
// ^ lol this makes everything look weird but I'll try it
tcT > using V = vector<T>;
tcT, size_t SZ > using AR = array<T, SZ>;
using vi = V<int>;
using vb = V<bool>;
using vl = V<ll>;
using vd = V<db>;
using vs = V<str>;
using vpi = V<pi>;
using vpl = V<pl>;
using vpd = V<pd>;

// vectors
// oops size(x), rbegin(x), rend(x) need C++17
#define sz(x) int((x).size())
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define lb lower_bound
#define ub upper_bound
tcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT > int upb(V<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

// loops
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define rep(a) F0R(_, a)
#define each(a, x) for (auto &a : x)

const int MOD = (int)1e9 + 7;  // 998244353;
const int MX = (int)2e5 + 5;
const ll BIG = 1e18;  // not too close to LLONG_MAX
const db PI = acos((db)-1);
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};  // for every grid problem!!
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;

// bitwise ops
// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
constexpr int pct(int x) { return __builtin_popcount(x); }  // # of bits set
constexpr int bits(int x) {  // assert(x >= 0); // make C++11 compatible until
	                         // USACO updates ...
	return x == 0 ? 0 : 31 - __builtin_clz(x);
}  // floor(log2(x))
constexpr int p2(int x) { return 1 << x; }
constexpr int msk2(int x) { return p2(x) - 1; }

ll cdiv(ll a, ll b) {
	return a / b + ((a ^ b) > 0 && a % b);
}  // divide a by b rounded up
ll fdiv(ll a, ll b) {
	return a / b - ((a ^ b) < 0 && a % b);
}  // divide a by b rounded down

tcT > bool ckmin(T &a, const T &b) {
	return b < a ? a = b, 1 : 0;
}  // set a = min(a,b)
tcT > bool ckmax(T &a, const T &b) {
	return a < b ? a = b, 1 : 0;
}  // set a = max(a,b)

tcTU > T fstTrue(T lo, T hi, U f) {
	++hi;
	assert(lo <= hi);  // assuming f is increasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo) / 2;
		f(mid) ? hi = mid : lo = mid + 1;
	}
	return lo;
}
tcTU > T lstTrue(T lo, T hi, U f) {
	--lo;
	assert(lo <= hi);  // assuming f is decreasing
	while (lo < hi) {  // find first index such that f is true
		T mid = lo + (hi - lo + 1) / 2;
		f(mid) ? lo = mid : hi = mid - 1;
	}
	return lo;
}
tcT > void remDup(vector<T> &v) {  // sort and remove duplicates
	sort(all(v));
	v.erase(unique(all(v)), end(v));
}
tcTU > void safeErase(T &t, const U &u) {
	auto it = t.find(u);
	assert(it != end(t));
	t.erase(it);
}

inline namespace IO {
#define SFINAE(x, ...)                                                         \
	template <class, class = void> struct x : std::false_type {};              \
	template <class T> struct x<T, std::void_t<__VA_ARGS__>> : std::true_type {}

SFINAE(DefaultI, decltype(std::cin >> std::declval<T &>()));
SFINAE(DefaultO, decltype(std::cout << std::declval<T &>()));
SFINAE(IsTuple, typename std::tuple_size<T>::type);
SFINAE(Iterable, decltype(std::begin(std::declval<T>())));

template <class T> constexpr char Space(const T &) {
	return (Iterable<T>::value or IsTuple<T>::value) ? '\n' : ' ';
}

template <auto &is> struct Reader {
	template <class T> void Impl(T &t) {
		if constexpr (DefaultI<T>::value) is >> t;
		else if constexpr (Iterable<T>::value) {
			for (auto &x : t) Impl(x);
		} else if constexpr (IsTuple<T>::value) {
			std::apply([this](auto &...args) { (Impl(args), ...); }, t);
		} else static_assert(IsTuple<T>::value, "No matching type for read");
	}
	template <class... Ts> void read(Ts &...ts) { ((Impl(ts)), ...); }
};

template <class... Ts> void re(Ts &...ts) { Reader<cin>{}.read(ts...); }
#define def(t, args...)                                                        \
	t args;                                                                    \
	re(args);

template <auto &os, bool debug> struct Writer {
	string comma() const { return debug ? "," : ""; }
	template <class T> void Impl(T const &t) const {
		if constexpr (DefaultO<T>::value) os << t;
		else if constexpr (Iterable<T>::value) {
			if (debug) os << '{';
			int i = 0;
			for (auto &&x : t)
				((i++) ? (os << comma() << Space(x), Impl(x)) : Impl(x));
			if (debug) os << '}';
		} else if constexpr (IsTuple<T>::value) {
			if (debug) os << '(';
			std::apply(
			    [this](auto const &...args) {
				    int i = 0;
				    (((i++) ? (os << comma() << " ", Impl(args)) : Impl(args)),
				     ...);
			    },
			    t);
			if (debug) os << ')';
		} else static_assert(IsTuple<T>::value, "No matching type for print");
	}
	template <class T> void ImplWrapper(T const &t) const {
		if (debug) os << "\033[0;31m";
		Impl(t);
		if (debug) os << "\033[0m";
	}
	template <class... Ts> void print(Ts const &...ts) const {
		((Impl(ts)), ...);
	}
	template <class F, class... Ts>
	void print_with_sep(const std::string &sep, F const &f,
	                    Ts const &...ts) const {
		ImplWrapper(f), ((os << sep, ImplWrapper(ts)), ...), os << '\n';
	}
	void print_with_sep(const std::string &) const { os << '\n'; }
};

template <class... Ts> void pr(Ts const &...ts) {
	Writer<cout, false>{}.print(ts...);
}
template <class... Ts> void ps(Ts const &...ts) {
	Writer<cout, false>{}.print_with_sep(" ", ts...);
}
}  // namespace IO

inline namespace Debug {
template <typename... Args> void err(Args... args) {
	Writer<cerr, true>{}.print_with_sep(" | ", args...);
}

void err_prefix(str func, int line, string args) {
	cerr << "\033[0;31m\u001b[1mDEBUG\033[0m"
	     << " | "
	     << "\u001b[34m" << func << "\033[0m"
	     << ":"
	     << "\u001b[34m" << line << "\033[0m"
	     << " - "
	     << "[" << args << "] = ";
}

#ifdef LOCAL
#define dbg(args...) err_prefix(__FUNCTION__, __LINE__, #args), err(args)
#else
#define dbg(...)
#endif

const auto beg_time = std::chrono::high_resolution_clock::now();
// https://stackoverflow.com/questions/47980498/accurate-c-c-clock-on-a-multi-core-processor-with-auto-overclock?noredirect=1&lq=1
double time_elapsed() {
	return chrono::duration<double>(std::chrono::high_resolution_clock::now() -
	                                beg_time)
	    .count();
}
}  // namespace Debug

inline namespace FileIO {
void setIn(str s) { freopen(s.c_str(), "r", stdin); }
void setOut(str s) { freopen(s.c_str(), "w", stdout); }
void setIO(str s = "") {
	cin.tie(0)->sync_with_stdio(0);  // unsync C / C++ I/O streams
	cout << fixed << setprecision(12);
	// cin.exceptions(cin.failbit);
	// throws exception when do smth illegal
	// ex. try to read letter into int
	if (sz(s)) setIn(s + ".in"), setOut(s + ".out");  // for old USACO
}
}  // namespace FileIO

// struct Bus {
// 	ll T;
// 	int W;
// 	// bool operator<(const Bus &o) const { return W < o.W; }
// };

// V<Bus> buses;

V<vl> arrival_times;
V<vi> by_arrival_times;
vi S, W;
int X;

pair<ll, int> get_pair(int i, int x) {
	return mp(arrival_times.at(i).at(x), W.at(x));
}

struct {
	ll tot_shift_left = 0;
	map<ll, ll> m;
	void shift_left(ll c) {  // f(x) -> y
		// f_new(x-c) = y
		tot_shift_left += c;
	}
	ll query(ll x) {
		x += tot_shift_left;
		auto it = m.ub(x);
		if (it != begin(m)) ckmax(x, prev(it)->s);
		return x;
	}
	void limit(ll x, ll y) {
		x += tot_shift_left;
		auto it = m.ub(x);
		if (it != begin(m) && prev(it)->s >= y) return;
		m[x] = y;
		it = m.find(x);
		while (next(it) != end(m) && next(it)->s <= y) m.erase(next(it));
	}
} Container;

void init(int L, int N, std::vector<long long> T, std::vector<int> _W, int _X,
          int M, std::vector<int> _S) {
	W = _W;
	X = _X;
	S = _S;
	assert(sz(S) == M);
	// F0R(i, N) buses.pb(Bus{T[i], W[i]});
	arrival_times.rsz(M);
	arrival_times[0] = T;

	// dbg("BEGIN INIT");
	FOR(i, 1, M) {
		arrival_times[i] = arrival_times[i - 1];
		F0R(j, N) {
			arrival_times[i][j] += (ll)W.at(j) * (S.at(i) - S.at(i - 1));
		}
		vi by_arrival_time(N);
		iota(all(by_arrival_time), 0);
		sort(all(by_arrival_time), [&](int x, int y) {
			return get_pair(i - 1, x) < get_pair(i - 1, y);
		});
		by_arrival_times.pb(by_arrival_time);
		ll max_arrival_time = 0;
		for (int j : by_arrival_time) {
			ckmax(max_arrival_time, arrival_times[i][j]);
			ckmax(arrival_times[i][j], max_arrival_time);
		}
	}
	// F0R(i, M) dbg(i, arrival_times[i]);
	// dbg("DONE INIT");
	R0F(i, M - 1) {
		vpl pairs;
		F0R(x, N) {
			pairs.pb({arrival_times[i][x],
			          Container.query(arrival_times[i + 1][x])});
		}
		Container.shift_left((ll)X * (S[i + 1] - S[i]));
		for (auto [p0, p1] : pairs) Container.limit(p0 + 1, p1);
	}
}

long long arrival_time(long long Y) {
	return Container.query(Y);
	// F0R(i, sz(S) - 1) {  // S[i] -> S[i+1]
	// 	int j = lstTrue(0, sz(by_arrival_times[i]) - 1, [&](int idx) {
	// 		return get_pair(i, by_arrival_times[i][idx]) < mp(Y, X);
	// 	});
	// 	// if (j != -1) {
	// 	// 	dbg(i, j, by_arrival_times[i][j],
	// 	// 	    get_pair(i, by_arrival_times[i][j]));
	// 	// }
	// 	// dbg(i, j);
	// 	Y += (ll)X * (S.at(i + 1) - S.at(i));
	// 	if (j >= 0)
	// 		ckmax(Y, arrival_times.at(i + 1).at(by_arrival_times.at(i).at(j)));
	// 	// dbg(Y);
	// }
	// return Y;
}

Compilation message

overtaking.cpp: In function 'void FileIO::setIn(str)':
overtaking.cpp:244:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 | void setIn(str s) { freopen(s.c_str(), "r", stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
overtaking.cpp: In function 'void FileIO::setOut(str)':
overtaking.cpp:245:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  245 | void setOut(str s) { freopen(s.c_str(), "w", stdout); }
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 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 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 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 600 KB Output is correct
11 Correct 1 ms 348 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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 4 ms 600 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 4 ms 856 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 4 ms 856 KB Output is correct
14 Correct 3 ms 600 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 3 ms 600 KB Output is correct
17 Correct 3 ms 600 KB Output is correct
18 Correct 4 ms 600 KB Output is correct
19 Correct 3 ms 600 KB Output is correct
20 Correct 3 ms 600 KB Output is correct
21 Correct 2 ms 344 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 2 ms 344 KB Output is correct
24 Correct 2 ms 344 KB Output is correct
25 Correct 2 ms 344 KB Output is correct
26 Correct 2 ms 348 KB Output is correct
27 Correct 2 ms 600 KB Output is correct
28 Correct 2 ms 344 KB Output is correct
29 Correct 2 ms 344 KB Output is correct
30 Correct 2 ms 344 KB Output is correct
31 Correct 2 ms 348 KB Output is correct
32 Correct 3 ms 1112 KB Output is correct
33 Correct 3 ms 1112 KB Output is correct
34 Correct 3 ms 1112 KB Output is correct
35 Correct 4 ms 1112 KB Output is correct
36 Correct 3 ms 1112 KB Output is correct
37 Correct 4 ms 1112 KB Output is correct
38 Correct 2 ms 344 KB Output is correct
39 Correct 2 ms 344 KB Output is correct
40 Correct 3 ms 600 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 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 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 4 ms 860 KB Output is correct
18 Correct 4 ms 856 KB Output is correct
19 Correct 3 ms 600 KB Output is correct
20 Correct 4 ms 856 KB Output is correct
21 Correct 3 ms 600 KB Output is correct
22 Correct 3 ms 600 KB Output is correct
23 Correct 3 ms 600 KB Output is correct
24 Correct 3 ms 600 KB Output is correct
25 Correct 4 ms 600 KB Output is correct
26 Correct 3 ms 600 KB Output is correct
27 Correct 3 ms 600 KB Output is correct
28 Correct 2 ms 344 KB Output is correct
29 Correct 1 ms 344 KB Output is correct
30 Correct 2 ms 344 KB Output is correct
31 Correct 2 ms 344 KB Output is correct
32 Correct 2 ms 344 KB Output is correct
33 Correct 2 ms 348 KB Output is correct
34 Correct 2 ms 600 KB Output is correct
35 Correct 2 ms 344 KB Output is correct
36 Correct 2 ms 344 KB Output is correct
37 Correct 2 ms 344 KB Output is correct
38 Correct 2 ms 348 KB Output is correct
39 Correct 3 ms 1112 KB Output is correct
40 Correct 3 ms 1112 KB Output is correct
41 Correct 3 ms 1112 KB Output is correct
42 Correct 4 ms 1112 KB Output is correct
43 Correct 3 ms 1112 KB Output is correct
44 Correct 4 ms 1112 KB Output is correct
45 Correct 2 ms 344 KB Output is correct
46 Correct 2 ms 344 KB Output is correct
47 Correct 3 ms 600 KB Output is correct
48 Correct 293 ms 12628 KB Output is correct
49 Correct 308 ms 13136 KB Output is correct
50 Correct 320 ms 13136 KB Output is correct
51 Correct 313 ms 13392 KB Output is correct
52 Correct 308 ms 13136 KB Output is correct
53 Correct 317 ms 13392 KB Output is correct
54 Correct 327 ms 13136 KB Output is correct
55 Correct 240 ms 12356 KB Output is correct
56 Correct 266 ms 12628 KB Output is correct
57 Correct 271 ms 12896 KB Output is correct
58 Correct 277 ms 12880 KB Output is correct
59 Correct 288 ms 12624 KB Output is correct
60 Correct 266 ms 12880 KB Output is correct
61 Correct 282 ms 12632 KB Output is correct
62 Correct 3 ms 856 KB Output is correct
63 Correct 2 ms 600 KB Output is correct
64 Correct 135 ms 6528 KB Output is correct
65 Correct 138 ms 6480 KB Output is correct
66 Correct 245 ms 12464 KB Output is correct
67 Correct 297 ms 12492 KB Output is correct
68 Correct 288 ms 12492 KB Output is correct
69 Correct 837 ms 74968 KB Output is correct
70 Correct 834 ms 74828 KB Output is correct
71 Correct 843 ms 75084 KB Output is correct
72 Correct 1025 ms 56720 KB Output is correct
73 Correct 825 ms 74948 KB Output is correct
74 Correct 871 ms 75124 KB Output is correct
75 Correct 253 ms 12548 KB Output is correct
76 Correct 252 ms 12624 KB Output is correct
77 Correct 260 ms 12624 KB Output is correct
78 Correct 476 ms 28320 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 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 0 ms 344 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 600 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 1 ms 344 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 344 KB Output is correct
27 Correct 4 ms 600 KB Output is correct
28 Correct 4 ms 860 KB Output is correct
29 Correct 4 ms 856 KB Output is correct
30 Correct 3 ms 600 KB Output is correct
31 Correct 4 ms 856 KB Output is correct
32 Correct 3 ms 600 KB Output is correct
33 Correct 3 ms 600 KB Output is correct
34 Correct 3 ms 600 KB Output is correct
35 Correct 3 ms 600 KB Output is correct
36 Correct 4 ms 600 KB Output is correct
37 Correct 3 ms 600 KB Output is correct
38 Correct 3 ms 600 KB Output is correct
39 Correct 2 ms 344 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 2 ms 344 KB Output is correct
42 Correct 2 ms 344 KB Output is correct
43 Correct 2 ms 344 KB Output is correct
44 Correct 2 ms 348 KB Output is correct
45 Correct 2 ms 600 KB Output is correct
46 Correct 2 ms 344 KB Output is correct
47 Correct 2 ms 344 KB Output is correct
48 Correct 2 ms 344 KB Output is correct
49 Correct 2 ms 348 KB Output is correct
50 Correct 3 ms 1112 KB Output is correct
51 Correct 3 ms 1112 KB Output is correct
52 Correct 3 ms 1112 KB Output is correct
53 Correct 4 ms 1112 KB Output is correct
54 Correct 3 ms 1112 KB Output is correct
55 Correct 4 ms 1112 KB Output is correct
56 Correct 2 ms 344 KB Output is correct
57 Correct 2 ms 344 KB Output is correct
58 Correct 3 ms 600 KB Output is correct
59 Correct 293 ms 12628 KB Output is correct
60 Correct 308 ms 13136 KB Output is correct
61 Correct 320 ms 13136 KB Output is correct
62 Correct 313 ms 13392 KB Output is correct
63 Correct 308 ms 13136 KB Output is correct
64 Correct 317 ms 13392 KB Output is correct
65 Correct 327 ms 13136 KB Output is correct
66 Correct 240 ms 12356 KB Output is correct
67 Correct 266 ms 12628 KB Output is correct
68 Correct 271 ms 12896 KB Output is correct
69 Correct 277 ms 12880 KB Output is correct
70 Correct 288 ms 12624 KB Output is correct
71 Correct 266 ms 12880 KB Output is correct
72 Correct 282 ms 12632 KB Output is correct
73 Correct 3 ms 856 KB Output is correct
74 Correct 2 ms 600 KB Output is correct
75 Correct 135 ms 6528 KB Output is correct
76 Correct 138 ms 6480 KB Output is correct
77 Correct 245 ms 12464 KB Output is correct
78 Correct 297 ms 12492 KB Output is correct
79 Correct 288 ms 12492 KB Output is correct
80 Correct 837 ms 74968 KB Output is correct
81 Correct 834 ms 74828 KB Output is correct
82 Correct 843 ms 75084 KB Output is correct
83 Correct 1025 ms 56720 KB Output is correct
84 Correct 825 ms 74948 KB Output is correct
85 Correct 871 ms 75124 KB Output is correct
86 Correct 253 ms 12548 KB Output is correct
87 Correct 252 ms 12624 KB Output is correct
88 Correct 260 ms 12624 KB Output is correct
89 Correct 476 ms 28320 KB Output is correct
90 Correct 307 ms 14928 KB Output is correct
91 Correct 539 ms 38596 KB Output is correct
92 Correct 558 ms 38732 KB Output is correct
93 Correct 532 ms 38616 KB Output is correct
94 Correct 527 ms 38516 KB Output is correct
95 Correct 544 ms 38668 KB Output is correct
96 Correct 551 ms 38732 KB Output is correct
97 Correct 246 ms 14672 KB Output is correct
98 Correct 513 ms 38036 KB Output is correct
99 Correct 490 ms 38460 KB Output is correct
100 Correct 496 ms 38056 KB Output is correct
101 Correct 496 ms 38440 KB Output is correct
102 Correct 493 ms 38224 KB Output is correct
103 Correct 488 ms 38256 KB Output is correct
104 Correct 363 ms 31052 KB Output is correct
105 Correct 368 ms 33356 KB Output is correct
106 Correct 599 ms 42180 KB Output is correct
107 Correct 537 ms 41936 KB Output is correct
108 Correct 532 ms 42060 KB Output is correct
109 Correct 534 ms 42060 KB Output is correct
110 Correct 533 ms 42064 KB Output is correct
111 Correct 1266 ms 100428 KB Output is correct
112 Correct 1286 ms 100700 KB Output is correct
113 Correct 1581 ms 101796 KB Output is correct
114 Correct 1753 ms 64916 KB Output is correct
115 Correct 1437 ms 101536 KB Output is correct
116 Correct 1353 ms 101276 KB Output is correct
117 Correct 558 ms 40012 KB Output is correct
118 Correct 511 ms 40128 KB Output is correct
119 Correct 510 ms 39240 KB Output is correct
120 Correct 560 ms 40276 KB Output is correct
121 Correct 549 ms 41148 KB Output is correct
122 Correct 865 ms 50436 KB Output is correct
123 Correct 1895 ms 64788 KB Output is correct
124 Correct 1796 ms 57896 KB Output is correct
125 Correct 1596 ms 55212 KB Output is correct