Submission #1299367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299367		Matthewwww	Tortoise (CEOI21_tortoise)	C++17	0 / 100	0 ms	332 KiB

tortoise

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	int ans = -n;
	vector<int> vt(n);
	for (int &i: vt) cin >> i;
	vector<vector<pair<int, int>>> dp(8*n, vector<pair<int, int>>(n+1, {-n, -n}));
	int prev = -n-n-n;
	vector<int> next(n, n+n+n+n+n);
	next.back() = vt.back() < 0 ? n-1 : next.back();
	for (int i = n-1; i--;) next[i] = vt[i] < 0 ? i : next[i+1];
	dp[0][0] = {0, 0};
	for (int j = 0; j < n; j++) for (int i = 0; i < 8*n; i++) {
		if (vt[j] < 0) {
			dp[i][j].f = dp[i][j].s = max(dp[i][j].f, dp[i][j].s);
			ans = max(ans, dp[i][j].f);
			if (i < 4*n) {
				dp[i+1][j+1].f = max(dp[i+1][j+1].f, dp[i][j].f);
				dp[i+1][j+1].s = max(dp[i+1][j+1].s, dp[i][j].s);
			}
			prev = j;
		} else {
			// go left
			if (i < 4*n) {
				if (next[j] < n) {
					dp[i][j].s = max(dp[i][j].f, dp[i][j].s);
					int d = next[j]-j;
					if (i-d >= 0) dp[i][j].s = max(dp[i][j].s, dp[i-d][next[j]].f);
					for (int b = 1; (i+(b-1)*d*2) <= j*2 && b <= vt[j]; b++) 
						dp[i+d*b*2-d][next[j]].f = max(dp[i+d*b*2-d][next[j]].f, dp[i][j].s+b);
				}
				dp[i+1][j+1].f = max(dp[i+1][j+1].f, dp[i][j].f);
				if (prev >= 0) {
					int d = j-prev;
					for (int b = 1; (i+(b-1)*d*2) <= j*2 && b <= vt[j]; b++) { // process .s first
						dp[i+d*b*2+1][j+1].f = max(dp[i+d*b*2+1][j+1].f, dp[i][j].f+b);
						if (next[j] < n) 
							dp[i+d*b*2-d-d+next[j]-j][next[j]].f = max(dp[i+d*b*2-d-d+next[j]-j][next[j]].f, dp[i][j].f+b);
					}
				}
			}
			ans = max(ans, dp[i][j].f);
			ans = max(ans, dp[i][j].s);
		}
	}
	for (int i = 0; i < 8*n; i++) ans = max(ans, max(dp[i][n].f, dp[i][n].s));
	int tot = 0;
	for (int i: vt) if (i > 0) tot += i;
	cout << tot-ans << "\n";
}

// no llama :(

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27