Submission #1166809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166809		tamyte	Potatoes and fertilizers (LMIO19_bulves)	C++20	0 / 100	1 ms	328 KiB

bulves

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


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i] >> b[i];
	}
	stack<pair<int, int>> right, left;
	for (int i = n - 1; i >= 0; --i) {
		if (a[i] > 0) right.push({a[i], i});
	}
	ll res = 0;
	for (int i = 0; i < n; ++i) {
		while (right.size() && right.top().second < i) {
			left.push(right.top());
			right.pop();
		}
		while (b[i] > 0) {
			int mn = INT_MAX;
			if (right.size()) {
				mn = min(mn, abs(i - right.top().second));
			}
			if (left.size()) {
				mn = min(mn, abs(i - left.top().second));
			}
			if (right.size() && mn == abs(i - right.top().second)) {
				int need = min(b[i], right.top().first);
				b[i] -= need;
				right.top().first -= need;
				res += 1LL * need * abs(i - right.top().second);
			} else {
				int need = min(b[i], left.top().first);
				b[i] -= need;
				left.top().first -= need;
				res += 1LL * need * abs(i - left.top().second);
			}
			while (left.size() && left.top().first == 0) {
				left.pop();
			}
			while (right.size() && right.top().first == 0) {
				right.pop();
			}
		}
	}
	cout << res << endl;
}

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