oj.uz

Submission #1016021

# Submission time Handle Problem Language Result Execution time Memory
1016021 2024-07-07T09:57:01 Z vjudge1 Potatoes and fertilizers (LMIO19_bulves) C++17
24 / 100
 66 ms 18768 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 11 ms 2668 KB Output is correct
6 Correct 30 ms 7500 KB Output is correct
7 Correct 61 ms 14928 KB Output is correct
8 Correct 48 ms 13044 KB Output is correct
9 Correct 47 ms 12368 KB Output is correct
10 Correct 36 ms 10068 KB Output is correct
11 Correct 35 ms 10064 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 6 ms 1372 KB Output is correct
5 Correct 11 ms 2668 KB Output is correct
6 Correct 30 ms 7500 KB Output is correct
7 Correct 61 ms 14928 KB Output is correct
8 Correct 48 ms 13044 KB Output is correct
9 Correct 47 ms 12368 KB Output is correct
10 Correct 36 ms 10068 KB Output is correct
11 Correct 35 ms 10064 KB Output is correct
12 Correct 24 ms 7900 KB Output is correct
13 Correct 40 ms 12888 KB Output is correct
14 Correct 66 ms 18768 KB Output is correct
15 Incorrect 56 ms 16976 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -