Submission #236030

#	Time	Username	Problem	Language	Result	Execution time	Memory
236030		JustasZ	Potatoes and fertilizers (LMIO19_bulves)	C++14	54 / 100	1088 ms	163960 KiB

bulves

/*input
7
2 0
2 0
2 0
0 5
2 0
2 0
2 0
*/
#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define rd() abs((int)rng())
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
const int maxn = 2e5 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	ll ans = 0, prefa = 0, prefb = 0;
	vector<ll>diff(n);
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		prefa += a;
		prefb += b;
		if (i < n - 1) {
			ans += abs(prefa - prefb);
			diff[i] = prefa - prefb;
		}
	}

	ll need = prefa - prefb;
	vector<ll>dp(need + 1, -1e18);
	dp[0] = 0;
	for (int i = 0; i < n - 1; i++) {
		ll mx = 0;
		for (ll j = 0; j <= need; j++) {
			mx = max(mx, dp[j]);
			ll val = diff[i];
			dp[j] = -1e18;
			if (val > 0) {
				ll add = min(val, j) - (j - min(val, j));
				dp[j] = max(dp[j], mx + add);
			} else {
				dp[j] = max(dp[j], mx - j);
			}
		}
	}

	ll mx = 0;
	for (int i = 0; i <= need; i++) {
		mx = max(mx, dp[i]);
	}
	cout << ans - mx << "\n";
	return 0;
}

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