제출 #146931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
146931		Bruteforceman	Potatoes and fertilizers (LMIO19_bulves)	C++11	24 / 100	168 ms	11344 KiB

bulves

#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
int a[1000010], b[1000010];

int main(int argc, char const *argv[])
{
	ios_base :: sync_with_stdio (false);
	cin.tie (0);
	int n;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}
	priority_queue <pii> P;
	priority_queue <pii> Q;
	long long ans = 0;

	for(int i = 0; i < n; i++) {
		int cur = a[i];
		while(!P.empty() && cur > 0) {
			int x = P.top().first;
			int y = P.top().second;
			P.pop();
			long long match = min(cur, y);
			ans += match * abs(i - x);
			if(y > match) P.push(pii(x, y - match));
			cur -= match;
		}
		if(cur > 0) Q.push(pii(i, cur));

		cur = b[i];
		while(!Q.empty() && cur > 0) {
			int x = Q.top().first;
			int y = Q.top().second;
			Q.pop();
			long long match = min(cur, y);
			ans += match * abs(i - x);
			if(y > match) Q.push(pii(x, y - match));
			cur -= match;
		}
		if(cur > 0) P.push(pii(i, cur));
	}	
	cout << ans << endl;
	return 0;
}

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