Submission #1002855

# Submission time Handle Problem Language Result Execution time Memory
1002855 2024-06-19T20:45:15 Z Lobo Cigle (COI21_cigle) C++17
0 / 100
2 ms 2480 KB
#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;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2480 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 2 ms 2396 KB Output is correct
5 Correct 2 ms 2396 KB Output is correct
6 Incorrect 2 ms 2396 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Halted 0 ms 0 KB -