Submission #476577

#	Time	Username	Problem	Language	Result	Execution time	Memory
476577		idiot123	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	204 ms	19316 KiB

bulves

#include<bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	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 < 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);
	}
	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 * x;
	}
	cout<<result;
	return 0;
}

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