oj.uz

Submission #146931

# Submission time Handle Problem Language Result Execution time Memory
146931 2019-08-26T16:56:19 Z Bruteforceman Potatoes and fertilizers (LMIO19_bulves) C++11
24 / 100
 168 ms 11344 KB 
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
int a[1000010], b[1000010];

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie (0);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	priority_queue <pii> P;
	priority_queue <pii> Q;
	long long ans = 0;

	for(int i = 0; i < n; i++) {
		int cur = a[i];
		while(!P.empty() && cur > 0) {
			int x = P.top().first;
			int y = P.top().second;
			P.pop();
			long long match = min(cur, y);
			ans += match * abs(i - x);
			if(y > match) P.push(pii(x, y - match));
			cur -= match;
		}
		if(cur > 0) Q.push(pii(i, cur));

		cur = b[i];
		while(!Q.empty() && cur > 0) {
			int x = Q.top().first;
			int y = Q.top().second;
			Q.pop();
			long long match = min(cur, y);
			ans += match * abs(i - x);
			if(y > match) Q.push(pii(x, y - match));
			cur -= match;
		}
		if(cur > 0) P.push(pii(i, cur));
	}	
	cout << ans << endl;
	return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 14 ms 1016 KB Output is correct
5 Correct 26 ms 1784 KB Output is correct
6 Correct 81 ms 5628 KB Output is correct
7 Correct 168 ms 11176 KB Output is correct
8 Correct 132 ms 11344 KB Output is correct
9 Correct 120 ms 8532 KB Output is correct
10 Correct 71 ms 6192 KB Output is correct
11 Correct 75 ms 6264 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 14 ms 1016 KB Output is correct
5 Correct 26 ms 1784 KB Output is correct
6 Correct 81 ms 5628 KB Output is correct
7 Correct 168 ms 11176 KB Output is correct
8 Correct 132 ms 11344 KB Output is correct
9 Correct 120 ms 8532 KB Output is correct
10 Correct 71 ms 6192 KB Output is correct
11 Correct 75 ms 6264 KB Output is correct
12 Incorrect 42 ms 3064 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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