Submission #473507

#	Time	Username	Problem	Language	Result	Execution time	Memory
473507		Fgdxx	Potatoes and fertilizers (LMIO19_bulves)	C++17	30 / 100	541 ms	66036 KiB

bulves

#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 < 30*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;
		long long x1 = q.top(); q.pop(); long long x2 = q.top();//pochodna na x1, x2 0 wiec x1 niepotrzebne
		shift += a - b;
		x2 += shift;
		if(x2 < 0){//w przeciwnym wypadku nic sie nie dzieje
			val -= x2;
		}
		q.push(-shift);
		q.push(-shift);
	}
	//cout<<q.top() + shift<<" "<<val<<"\n\n";
	//obliczamy roznice miedzy 0 a tam gdzie znamy val
	long long diff = 0;
	long long slope = -1;
	long long x = q.top()+shift;
	if(x > 0){
		diff = x;
	}else{
		while(x < 0){
			q.pop();
			slope++;
			long long newX = min(q.top()+shift, 0ll);
			diff += slope * (newX - x);
			x = newX;
		}
	}
	cout<<(val + diff);
}

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:13:13: warning: unused variable 'x1' [-Wunused-variable]
   13 |   long long x1 = q.top(); q.pop(); long long x2 = q.top();//pochodna na x1, x2 0 wiec x1 niepotrzebne
      |             ^~

• Subtask 1: 0 / 24
• Subtask 2: 0 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 0 / 36