Submission #707973

#	Time	Username	Problem	Language	Result	Execution time	Memory
707973		arcane	Cigle (COI21_cigle)	C++17	100 / 100	470 ms	391888 KiB

cigle

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, ptr, cnt, ans = 0; cin >> n;
	int arr[n], dp[n][n], pref[n][n], prefs[n + 1]; for (int i = 0; i < n; i++) cin >> arr[i];
	prefs[0] = 0; for (int i = 0; i < n; i++) prefs[i + 1] = prefs[i] + arr[i];
	for (int i = 1; i < n; i++) fill(dp[i], dp[i] + n, 0);
	fill(dp[0], dp[0] + n, 0);
	for (int i = 1; i < n; i++){
		ptr = i - 1; cnt = 0;
		for (int j = 0; j < n; j++){
			if (!j) pref[i - 1][j] = dp[j][i - 1];
			else pref[i - 1][j] = max(dp[j][i - 1], pref[i - 1][j - 1]);
		}
		for (int j = i; j < n; j++){
			if (j == i) dp[i][j] = pref[i - 1][i - 1];
			else{
				dp[i][j] = dp[i][j - 1];
				if (ptr >= 0 and prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]){
					if (prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]) cnt += 1;
					dp[i][j] = max(dp[i][j], pref[i - 1][ptr] + cnt);
				}
				while (ptr >= 0 and prefs[i] - prefs[ptr + 1] < prefs[j] - prefs[i]){
					ptr--;
					if (ptr >= 0 and prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]){
						if (prefs[i] - prefs[ptr + 1] == prefs[j] - prefs[i]) cnt += 1;
						dp[i][j] = max(dp[i][j], pref[i - 1][ptr] + cnt);
					}
				}
			} 
		}
	}
	for (int i = 0; i < n; i++) ans = max(ans, dp[i][n - 1]);
	cout << ans << '\n';
}

• Subtask 1: 9 / 9
• Subtask 2: 11 / 11
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 52 / 52