Submission #476573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
476573	2021-09-27T16:48:59 Z	idiot123	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	1000 ms	27580 KB

bulves

#include<bits/stdc++.h>

using namespace std;

int main(){
	int N; cin>>N;
	vector<long long> t(N);
	for(int i = 0; i < N; i++){
		int a, b; cin>>a>>b;
		t[i] = a - b;
	}
	priority_queue<long long, vector<long long>, greater<long long>> q;
	for(int i = 0; i < 2*N; i++)q.push(0);
	long long shift = 0;
	long long val = 0;
	for(int i = 1; i <= N; i++){
		//wywalamy pierwszy punkt
		q.pop();
		//przesuwamy
		shift += t[i-1];
		//pobieramy pozycje pierwszego punktu
		long long x = q.top() + shift;
		if(x <= 0){
			val += abs(x);
			q.push(-shift); q.push(-shift);
		}else{
			q.push(-shift); q.push(-shift);
		}
	}
	long long x = q.top() + shift;
	long long result;
	if(x >= 0){
		result = val + x;
	}else{
		result = val;
		int slope = 0;
		q.pop();
		while(q.top() + shift <= 0){
			result += slope * (q.top() + shift - x);
			x = q.top() + shift;
			q.pop();
			slope++;
		}
		result += slope *(0 - x);
	}
	cout<<result;
	return 0;
}

Subtask #1

0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	38 ms	3176 KB	Output is correct
5	Correct	73 ms	5920 KB	Output is correct
6	Correct	248 ms	13868 KB	Output is correct
7	Correct	431 ms	27580 KB	Output is correct
8	Execution timed out	1092 ms	25544 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	38 ms	3176 KB	Output is correct
5	Correct	73 ms	5920 KB	Output is correct
6	Correct	248 ms	13868 KB	Output is correct
7	Correct	431 ms	27580 KB	Output is correct
8	Execution timed out	1092 ms	25544 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-

Subtask #3

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	0 ms	296 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	2 ms	460 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	2 ms	460 KB	Output is correct
12	Correct	2 ms	332 KB	Output is correct
13	Correct	3 ms	460 KB	Output is correct
14	Correct	3 ms	460 KB	Output is correct
15	Correct	2 ms	460 KB	Output is correct
16	Correct	3 ms	460 KB	Output is correct
17	Correct	2 ms	460 KB	Output is correct
18	Correct	3 ms	460 KB	Output is correct

Subtask #5

0 / 36.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	460 KB	Output is correct
3	Correct	3 ms	460 KB	Output is correct
4	Correct	0 ms	296 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	2 ms	460 KB	Output is correct
8	Correct	2 ms	460 KB	Output is correct
9	Correct	2 ms	460 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	38 ms	3176 KB	Output is correct
12	Correct	73 ms	5920 KB	Output is correct
13	Correct	248 ms	13868 KB	Output is correct
14	Correct	431 ms	27580 KB	Output is correct
15	Execution timed out	1092 ms	25544 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-