Submission #473488

#	Time	Username	Problem	Language	Result	Execution time	Memory
473488		Fgdxx	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	372 ms	10964 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 < 2*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 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36