Submission #420799

#	Time	Username	Problem	Language	Result	Execution time	Memory
420799		maximath_1	Cigle (COI21_cigle)	C++11	100 / 100	296 ms	67376 KiB

cigle

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
#include <random>
#include <deque>
using namespace std;

mt19937 rng(420691273);
#define ll long long
const int MX = 5e3 + 5;

int n, v[MX], dp[MX][MX];

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n;
	for(int i = 0; i < n; i ++) cin >> v[i];

	for(int ps = 0; ps < n; ps ++){
		for(int l = 1; l <= ps; l ++)
			dp[l][ps] = max(dp[l][ps], dp[l - 1][ps]);

		int up = 0, dn = 0, cnt = -1;
		for(int l = ps, r = ps + 1; l >= 0 && r < n;){
			if(up == dn){
				cnt ++;
				dp[ps + 1][r] = max(dp[ps + 1][r], dp[l][ps] + cnt);
				dn += v[l --]; up += v[r ++];
			}else if(up < dn)
				up += v[r ++];
			else if(up > dn)
				dn += v[l --];
		}

		for(int r = ps + 1; r < n; r ++)
			dp[ps + 1][r] = max(dp[ps + 1][r], dp[ps + 1][r - 1]);
	}

	int ans = 0;
	for(int l = 0; l < n; l ++)
		ans = max(ans, dp[l][n - 1]);
	cout << ans << endl;
	return 0;
}

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