Submission #1002715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002715		Juan	Cigle (COI21_cigle)	C++17	0 / 100	1048 ms	1876 KiB

cigle

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3+5;

int p[maxn], dp[maxn][maxn];
bool mark[2*maxn*maxn];

int calc(int r, int l, int c){
	int rt=0;
	for(int i=l; i<c; i++) mark[p[i]]=true;
	for(int i=c+1; i<r; i++) rt += mark[2*p[c]-p[i]];
	for(int i=l; i<c; i++) mark[p[i]]=false;
	return rt;
}

int main(){
	int n; cin >> n;
	vector<int> v(n+1);
	for(int i=1; i<=n; i++) cin >> v[i];
	for(int i=1; i<=n; i++) p[i] = p[i-1]+v[i];

	int dbg=12;
	for(int i=1; i<=n; i++){
		for(int j=1; j<i; j++){
			for(int k=j; k<i; k++){
				int val = calc(i,j,k);
				// if(i==dbg) cout << val << " ";
				dp[i][k+1] = max(dp[i][k+1], dp[k][j]+val);
			}
			// if(i==dbg) cout << endl;
		}
		// if(i==dbg) cout << endl;
	}

	// for(int i=0; i<=n; i++) cout << dp[i] << " ";
	// cout << endl;

	int ans=0;
	for(int i=0; i<=n; i++) ans = max(ans,dp[n][i]);
	cout << ans << '\n';
	// cout << dp[n] << '\n';
}

Compilation message (stderr)

cigle.cpp: In function 'int main()':
cigle.cpp:22:6: warning: unused variable 'dbg' [-Wunused-variable]
   22 |  int dbg=12;
      |      ^~~

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