Submission #708143

#	Time	Username	Problem	Language	Result	Execution time	Memory
708143		Matjaz	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	2 ms	340 KiB

bulves

#include<vector>
#include<iostream>
#include <stdlib.h> 
#include <algorithm>
#include <stack>

using namespace std;

int N;

int main(){
	cin >> N;
	vector<int> a(N), b(N);
	for (int i=0;i<N;i++) 
		cin >> a[i] >> b[i];

	int cost = 0;

	stack<pair<int,int>> left;
	stack<pair<int,int>> right;

	for (int i=N-1;i>0;i--){
		if (a[i] > b[i]) right.push({a[i] - b[i], i});
	}


	for (int i=0;i<N;i++){

		while (!right.empty() && right.top().second <= i) right.pop();
		if (a[i] == b[i]) continue;

		if (a[i] > b[i]) left.push({a[i] - b[i], i}); else {
			int deficit = b[i] - a[i];
			while (deficit > 0){
				if (left.empty()) {
					cost += abs(right.top().second - i) * min(deficit, right.top().first);
					if (deficit >= right.top().first){
						deficit -= right.top().first;
						right.pop();
					}  else {
						right.top().second -= deficit;
						deficit = 0;
					}
				} else if (right.empty()){
					cost += abs(left.top().second - i) * min(deficit, left.top().first);
					if (deficit >= left.top().first){
						deficit -= left.top().first;
						left.pop();
					}  else {
						left.top().second -= deficit;
						deficit = 0;
					}


				} else if (abs(left.top().second - i) > abs(right.top().second - i)) {
					cost += abs(right.top().second - i) * min(deficit, right.top().first);
					if (deficit >= right.top().first){
						deficit -= right.top().first;
						right.pop();
					}  else {
						right.top().second -= deficit;
						deficit = 0;
					}

				} else {
					cost += abs(left.top().second - i) * min(deficit, left.top().first);
					if (deficit >= left.top().first){
						deficit -= left.top().first;
						left.pop();
					}  else {
						left.top().second -= deficit;
						deficit = 0;
					}
				}
			}
		}
	}

	cout << cost << endl;

	return 0;
}

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