Submission #253216

#	Time	Username	Problem	Language	Result	Execution time	Memory
253216		Berted	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	198 ms	8632 KiB

bulves

#include <iostream>
#include <queue>
#define ll long long
using namespace std;

/*
	Transform the array into A - B
	We could change an operation into -1 +1 adjacent indices
	
	Transform the array into prefix sum
	Now, an operation changed A[i] into A[i] + 1 or A[i] - 1
	for 1 <= i < N. A[0] = 0, A[N] = SUM;
	
	Therefore the array must be transformed such that it is non-decreasing
	We can achieve this with slope trick.
*/

const ll INF = 1e18;

int n;
ll ar[500001], res = 0;
priority_queue<ll> pq;

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a, b; cin >> a >> b;
		ar[i] = a - b;
		if (i) ar[i] += ar[i - 1];
	}

	pq.push(0);

	for (int i = 0; i < n - 1; i++)
	{
		if (ar[i] < pq.top())
		{
			res += pq.top() - ar[i]; pq.pop();
			pq.push(max(ar[i], 0LL));
		}
		// cout << "Push at " << ar[i] << "\n";
		pq.push(max(ar[i], 0LL));
	}

	int i;
	ll pv = pq.top();
	for (i = 0; pq.top() > ar[n - 1]; i++)
	{
		res += (pv - pq.top()) * i;
		pv = pq.top(); pq.pop();
	}

	res += (pv - ar[n - 1]) * i;

	cout << res << "\n";
	return 0;
}

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