Submission #1342845

#TimeUsernameProblemLanguageResultExecution timeMemory
1342845ppmn_6Bikeparking (EGOI24_bikeparking)C++20
100 / 100
132 ms3956 KiB
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<class Key, class Compare = less<Key>>
using indexed_set = tree<Key, null_type, Compare, rb_tree_tag, tree_order_statistics_node_update>;

template<class Key, class Value, class Compare = less<Key>>
using indexed_map = tree<Key, Value, Compare, rb_tree_tag, tree_order_statistics_node_update>;

template<class Key>
using hash_set = gp_hash_table<
    Key, null_type, hash<Key>, equal_to<Key>, direct_mask_range_hashing<Key>, linear_probe_fn<>,
    hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>;
    
template<class Key, class Value>
using hash_map = gp_hash_table<
    Key, Value, hash<Key>, equal_to<Key>, direct_mask_range_hashing<Key>, linear_probe_fn<>,
    hash_standard_resize_policy<hash_exponential_size_policy<>, hash_load_check_resize_trigger<true>, true>>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, pf = 0, l = 0, r = 0;
	cin >> n;
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> y[i];
		pf += x[i];
		l += max(0, y[i] - pf);
		pf -= min(y[i], pf);
		r += y[i];
	}
	auto test = [&] (int k) {
		int p = 0, res1 = 0, res2 = 0, k_ori = k;
		vector<int> x2 = x;
		for (int i = 0; i < n; i++) {
			int cur = y[i] - min(k, y[i]);
			k -= min(k, y[i]);
			while (cur) {
				int d = min(cur, x2[p]);
				cur -= d;
				x2[p] -= d;
				if (p < i) {
					res1 += d;
				}
				if (!x2[p]) {
					p++;
				}
			}
		}
		k = k_ori + 1;
		x2 = x;
		p = 0;
		for (int i = 0; i < n; i++) {
			int cur = y[i] - min(k, y[i]);
			k -= min(k, y[i]);
			while (cur) {
				int d = min(cur, x2[p]);
				cur -= d;
				x2[p] -= d;
				if (p < i) {
					res2 += d;
				}
				if (!x2[p]) {
					p++;
				}
			}
		}
		return make_pair(res1, res2);
	};
	if (l == r) {
		cout << test(l).first - l;
		return 0;
	}
	r--;
	while (r - l > 2) {
		int m = (l + r) / 2;
		pair<int, int> res = test(m);
		if (res.second - res.first > 0) {
			l = m;
		}
		else {
			r = m;
		}
	}
	if (test(l).second - test(l).first <= 0) {
		cout << test(l).first - l;
	}
	else if (test(l + 1).second - test(l + 1).first <= 0) {
		cout << test(l + 1).first - l - 1;
	}
	else {
		cout << test(r).first - r;
	}
	
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...