Submission #1157442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157442		raczek	Cigle (COI21_cigle)	C++20	0 / 100	2 ms	2372 KiB

cigle

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X...) cerr<<"["#X"]: ", [](auto...$) {((cerr<<$<<"; "),...)<<endl;}(X)
#else 
#define debug(...){}
#endif
#define int long long
const int INF = 1e18+7;
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
#define eb emplace_back
int32_t main()
{
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	vector<int> a(n);
	for(auto& v : a) cin>>v;
	vector dp(n, vector(n, 0LL));
	for(int l=0;l<n;l++)
	{
		int pref = 0, suf = a[l], bty = 0;
		if(l-1 >= 0) pref = a[l-1];
		int x = l-1, y = l;
		int bst = 0;
		vector<int> prefMax;
		for(int i=0;i<l;i++)
			prefMax.eb(max(prefMax.size() ? prefMax.back() : 0, dp[i][l-1]));
		while(y < n && x >= 0)
		{
			dp[l][y] = prefMax[x]+bty;
			bst = max(bst, dp[l][y]);
			if(pref < suf)
			{
				x--;
				if(x >= 0) pref += a[x];
			}
			if(pref > suf)
			{
				y++;
				if(y < n) suf += a[y];
			}
			if(pref == suf)
			{
				dp[l][y] = prefMax[x]+bty;
				bst = max(bst, dp[l][y]);
				bty++;
				x--;
				if(x >= 0) pref += a[x];
			}
		}
		while(y < n) dp[l][y++] = bst;
	}
	int res = 0;
	for(int i=0;i<n;i++)
		res = max(res, dp[i][n-1]);
	cout<<res;
}

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