답안 #399558

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399558	2021-05-06T05:36:51 Z	ronnith	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	210 ms	13052 KB

bulves

#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();
			}
		}
	}

	vector<int> val;
	while ((int)pq.size()) {
		val.push_back(pq.top());
		pq.pop();
	}
	sort(val.begin(), val.end());

	for (auto& e : val) {
		if (e >= d[n - 1]) break;
		long long y = line.getY(e);
		line.m ++;
		line.c = y - line.m * e; 
	}

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

	return 0;
}

Subtask #1

0 / 24.0

#	결과	실행 시간	메모리	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	Correct	15 ms	1356 KB	Output is correct
5	Correct	37 ms	2472 KB	Output is correct
6	Correct	116 ms	6824 KB	Output is correct
7	Correct	106 ms	8260 KB	Output is correct
8	Incorrect	210 ms	13052 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	결과	실행 시간	메모리	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	Correct	15 ms	1356 KB	Output is correct
5	Correct	37 ms	2472 KB	Output is correct
6	Correct	116 ms	6824 KB	Output is correct
7	Correct	106 ms	8260 KB	Output is correct
8	Incorrect	210 ms	13052 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	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	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	332 KB	Output is correct
7	Correct	2 ms	340 KB	Output is correct
8	Correct	2 ms	332 KB	Output is correct
9	Correct	1 ms	332 KB	Output is correct
10	Correct	2 ms	332 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	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	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	2 ms	332 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	2 ms	460 KB	Output is correct
14	Correct	2 ms	460 KB	Output is correct
15	Correct	2 ms	460 KB	Output is correct
16	Correct	2 ms	460 KB	Output is correct
17	Correct	2 ms	460 KB	Output is correct
18	Correct	2 ms	332 KB	Output is correct

Subtask #5

0 / 36.0

#	결과	실행 시간	메모리	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	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	2 ms	332 KB	Output is correct
8	Correct	2 ms	340 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	332 KB	Output is correct
11	Correct	15 ms	1356 KB	Output is correct
12	Correct	37 ms	2472 KB	Output is correct
13	Correct	116 ms	6824 KB	Output is correct
14	Correct	106 ms	8260 KB	Output is correct
15	Incorrect	210 ms	13052 KB	Output isn't correct
16	Halted	0 ms	0 KB	-