Submission #1002855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002855		Lobo	Cigle (COI21_cigle)	C++17	0 / 100	2 ms	2480 KiB

cigle

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e18+10;

int32_t main() {
	// #ifndef ONLINE_JUDGE
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
	// #endif
	int n;
	cin >> n;
	vector<int> a(n+10);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}


	vector<vector<int>> dp(n+10,vector<int>(n+10,-inf));
	
	for(int i = 1; i <= n; i++) dp[1][i] = 0;
	int ans = 0;
	for(int i = 2; i <= n; i++) {
		int k = i;
		int sj = 0;
		int sk = 0;
		vector<int> qtd(n+10,0);
		// cout << i << endl;
		for(int j = i; j <= n; j++) {
			sj+= a[j];
			while(k-1 >= 1 && sk+a[k-1] <= sj) {
				k--;
				qtd[k] = (k == i-1 ? 0 : qtd[k+1]);
				sk+= a[k];
				if(sk == sj) qtd[k]++;
			}
			qtd[j] = (j == i ? 0 : qtd[j-1]);
			if(sj == sk) qtd[j]++;
		}
		vector<int> pfmaxdp(n+10,-inf);

		for(int j = 1; j <= i-1; j++) {
			pfmaxdp[j] = max(pfmaxdp[j-1],dp[j][i-1]);
		}
		k = i;
		sj = 0;
		sk = 0;
		int maxdpqtd = -inf;
		for(int j = i; j <= n; j++) {
			sj+= a[j];
			while(k-1 >= 1 && sk+a[k-1] <= sj) {
				k--;
				sk+= a[k];
			}
			maxdpqtd = max(maxdpqtd,dp[k][i-1]+(k == i-1 ? 0 : qtd[k+1]));
			dp[i][j] = max(maxdpqtd,pfmaxdp[k-1]+(j == i ? 0 : qtd[j-1]));
			// cout << " " << j << " " << k << " " << dp[i][j] << " " << qtd[k+1] << endl;
		}
	}

	for(int i = 1; i <= n; i++) {
		ans = max(ans,dp[i][n]);
	}
	cout << ans << endl;
}

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