Submission #1002846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002846		Juan	Cigle (COI21_cigle)	C++17	0 / 100	1070 ms	2324 KiB

cigle

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

int p[maxn], dp[maxn][maxn];
bool mark[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++) if(2*p[c]-p[i]<maxn*maxn) rt += mark[2*p[c]-p[i]];
	for(int i=l; i<c; i++) mark[p[i]]=false;
	return rt;
}

signed 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=6;
	bool dbg_on=false;
	int ans=0;
	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 && dbg_on) cout << val << " ";
				dp[i][k+1] = max(dp[i][k+1], dp[k][j]+val);
				ans = max(ans,dp[i][k+1]);
			}
			if(i==dbg && dbg_on) cout << endl;
		}
		if(i==dbg && dbg_on) 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';
}

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