oj.uz

Submission #708143

# Submission time Handle Problem Language Result Execution time Memory
708143 2023-03-11T06:21:16 Z Matjaz Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 2 ms 340 KB 

#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -