oj.uz

Submission #473489

# Submission time Handle Problem Language Result Execution time Memory
473489 2021-09-15T15:17:28 Z Fgdxx Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 417 ms 8636 KB 
#include<bits/stdc++.h>

using namespace std;

int main(){
	int n; cin>>n;
	priority_queue<int, vector<int>, greater<int>> q;
	for(int i = 0; i < 4*n; i++)q.push(0);
	long long shift = 0;
	long long val = 0;
	for(int i = 0; i < n; i++){
		int a, b; cin>>a>>b;
		q.pop(); long long x2 = q.top();//pochodna na x1, x2 0 wiec x1 niepotrzebne
		shift += a - b;
		x2 += shift;
		val += abs(x2);
		q.push(-shift);
	}
	//obliczamy roznice miedzy 0 a tam gdzie znamy val
	long long diff = 0;
	long long slope = 0;
	long long x = q.top();
	if(x > 0){
		diff = -x;
	}else{
		while(x < 0){
			q.pop();
			long long newX = min(q.top(), 0);
			diff += slope * (newX - x);
			slope++;
			x = newX;
		}
	}
	cout<<(val + diff);
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 34 ms 1348 KB Output is correct
5 Correct 71 ms 2368 KB Output is correct
6 Correct 197 ms 4540 KB Output is correct
7 Correct 417 ms 8636 KB Output is correct
8 Correct 336 ms 8544 KB Output is correct
9 Correct 321 ms 8608 KB Output is correct
10 Correct 260 ms 8632 KB Output is correct
11 Correct 259 ms 8628 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 34 ms 1348 KB Output is correct
5 Correct 71 ms 2368 KB Output is correct
6 Correct 197 ms 4540 KB Output is correct
7 Correct 417 ms 8636 KB Output is correct
8 Correct 336 ms 8544 KB Output is correct
9 Correct 321 ms 8608 KB Output is correct
10 Correct 260 ms 8632 KB Output is correct
11 Correct 259 ms 8628 KB Output is correct
12 Incorrect 103 ms 2368 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 36.0

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