Submission #1016021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016021		vjudge1	Potatoes and fertilizers (LMIO19_bulves)	C++17	24 / 100	66 ms	18768 KiB

bulves

#include <bits/stdc++.h>
using namespace std;

const long long inf = 1LL << 60;

int a[500008], b[500008], c[500008], d[500008];
long long cost[500008];

long long dp[2][30008];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	long long A = 0, B = 0, ans = 0;
	for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i], A += a[i], B += b[i], c[i] = a[i], d[i] = b[i];
	if (A == B) {
		int pt1 = 1, pt2 = 1, trans;
		while (pt2 <= n) {
			if (!a[pt1]) ++pt1;
			else if (!b[pt2]) ++pt2;
			else {
				trans = min(a[pt1], b[pt2]);
				a[pt1] -= trans; b[pt2] -= trans;
				ans += 1LL * trans * abs(pt1 - pt2);
			}
		}
		cout << ans;
	}
	else if (A == B + 1) {
		int pt = n, trans; ans = inf; long long cur = 0;
		for (int i = n; i; --i) {
			cost[i] = cost[i + 1];
			while (c[i]) {
				trans = min(c[i], d[pt]);
				c[i] -= trans; d[pt] -= trans; cost[i] += 1LL * trans * abs(i - pt);
				if (!c[i]) break;
				--pt;
			}
		}
		pt = 1;
		for (int i = 1; i <= n; ++i) if (a[i]) {
			while (a[i] && pt <= n) {
				trans = min(a[i], b[pt]);
				a[i] -= trans; b[pt] -= trans; cur += 1LL * trans * abs(i - pt);
				if (!a[i]) break;
				++pt;
			}
			if (pt <= n) ans = min(ans, cur - abs(i - pt) + cost[i + 1]);
			else ans = min(ans, cur);
		}
		cout << ans;
	}
	else {
		
	}
}

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