oj.uz

Submission #399553

# Submission time Handle Problem Language Result Execution time Memory
399553 2021-05-06T05:26:33 Z ronnith Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 145 ms 15228 KB 
#include <bits/stdc++.h>

using namespace std;

struct Line {
	long long m, c;
	Line() {}
	Line(long long mm, long long cc) : m(mm), c(cc) {}
	inline long long getY(long long x) { return m*x+c; }
};

const int N = (int)5e5;
int n, a[N], b[N];
long long d[N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;

	for (int i = 0;i < n;i ++) {
		cin >> a[i] >> b[i];
		d[i] = a[i] - b[i];
		if (i != 0) d[i] += d[i - 1];
	}

	Line line;
	priority_queue<int> pq;
	if (d[0] > 0) {
		pq.push(d[0]);
		line = Line(-1, d[0]);
	} else {
		line = Line(0, -d[0]);
	}

	for (int i = 1;i < n - 1;i ++) {
		if (d[i] >= 0) {
			pq.push(d[i]);
			pq.push(d[i]);
			pq.pop();
			line.m --;
			line.c += d[i];
		} else {
			if (line.m + 1 > 0) {
				line.m = 0;
				line.c += -d[i];
				while ((int)pq.size()) pq.pop();
			} else {
				line.m ++;
				line.c += -d[i];
				pq.pop();
			}
		}
	}

	while ((int)pq.size() && pq.top() < d[n - 1]) {
		long long y = line.getY(pq.top());
		line.m ++;
		line.c = y - line.m * pq.top(); 
		pq.pop();
	}

	cout << line.getY(d[n - 1]) << '\n';

	return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 14 ms 1580 KB Output is correct
5 Correct 28 ms 2912 KB Output is correct
6 Correct 79 ms 8660 KB Output is correct
7 Correct 106 ms 15044 KB Output is correct
8 Correct 130 ms 15164 KB Output is correct
9 Correct 111 ms 12708 KB Output is correct
10 Correct 106 ms 12392 KB Output is correct
11 Correct 106 ms 12280 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 14 ms 1580 KB Output is correct
5 Correct 28 ms 2912 KB Output is correct
6 Correct 79 ms 8660 KB Output is correct
7 Correct 106 ms 15044 KB Output is correct
8 Correct 130 ms 15164 KB Output is correct
9 Correct 111 ms 12708 KB Output is correct
10 Correct 106 ms 12392 KB Output is correct
11 Correct 106 ms 12280 KB Output is correct
12 Correct 39 ms 4632 KB Output is correct
13 Correct 96 ms 10144 KB Output is correct
14 Correct 113 ms 15064 KB Output is correct
15 Correct 131 ms 15228 KB Output is correct
16 Correct 145 ms 14440 KB Output is correct
17 Incorrect 104 ms 12260 KB Output isn't correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Incorrect 1 ms 332 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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