제출 #1166809

#제출 시각아이디문제언어결과실행 시간메모리
1166809tamytePotatoes and fertilizers (LMIO19_bulves)C++20
0 / 100
1 ms328 KiB
#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;
}
#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...