Submission #1157413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157413		raczek	Cigle (COI21_cigle)	C++20	20 / 100	1095 ms	2492 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 r=0;r<n;r++)
	{
		for(int l=0;l<=r;l++)
		{
			for(int x=0;x<l;x++)
			{
				vector<int> pref;
				for(int y=x;y<l;y++)
					pref.eb((pref.size() ? pref.back() : 0)+a[y]);
				vector<int> suf;
				for(int y=l;y<r;y++)
					suf.eb((suf.size() ? suf.back() : 0)+a[y]);
				for(auto& v : suf) v = pref.back() - v;
				reverse(suf.begin(), suf.end());
				vector<int> pr;
				merge(pref.begin(), pref.end(), suf.begin(), suf.end(), back_inserter(pr));
				debug(pr);
				int cnt = 0;
				for(int i=0;i<pr.size()-1;i++)
					if(pr[i] == pr[i+1])
						cnt++;
				dp[l][r] = max(dp[l][r], cnt + dp[x][l-1]);
			}
		}
	}
	int res = 0;
	for(int i=0;i<n;i++)
		res = max(res, dp[i][n-1]);
	cout<<res;
}

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