Submission #1166834

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166834		tamyte	Potatoes and fertilizers (LMIO19_bulves)	C++20	24 / 100	77 ms	10312 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n;


ll calc(vector<int> a, vector<int> b) {
	ll res = 0;
	stack<pair<int, int>> left, right;
	for (int i = n - 1; i >= 0; --i) {
		if (a[i] > 0) {
			right.push({a[i], i});
		}
	}
	for (int i = 0; i < n; ++i) {
		while (right.size() && right.top().second <= i) {
			left.push({right.top()});
			right.pop();
		}
		while (b[i] > 0) {
			if (left.size()) {
				int need = min(b[i], left.top().first);
				b[i] -= need;
				left.top().first -= need;
				int d = abs(i - left.top().second);
				res += 1LL * d * need;
			} else {
				int need = min(b[i], right.top().first);
				b[i] -= need;
				right.top().first -= need;
				int d = abs(i - right.top().second);
				res += 1LL * d * need;
			}
			while (left.size() && left.top().first == 0) left.pop();
			while (right.size() && right.top().first == 0) right.pop();
		}
	}
	return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	cin >> n;
	vector<int> a, b;
	a = vector<int>(n);
	b = vector<int>(n);
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
		int need = min(a[i], b[i]);
		a[i] -= need;
		b[i] -= need;
	}
	res = calc(a, b);
	reverse(begin(a), end(a));
	reverse(begin(b), end(b));
	res = min(res, calc(a, b));
	// cout << "CNT: " << cnt << endl;
	cout << res << endl;
}

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36