Submission #1002832

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002832		PagodePaiva	Cigle (COI21_cigle)	C++17	33 / 100	275 ms	6748 KiB

cigle

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

const int N =510;
const int inf = 1e9;

int n;
int dp[N][N][2];
int v[N];
int mark[N*N];

const int debug = 0;

int main(){
	cin >> n;
	for(int i = 1;i <= n;i++)
		cin >> v[i];
	for(int i = 1;i <= n;i++){
		dp[1][i][0] = 0;
		dp[1][i][1] = -inf;
	}		
	for(int i = 1;i < n;i++){
		for(int j = i;j < n;j++){
			//
			int t = 0;
			int l = i, r = j;
			vector <int> bons;
			t += v[i];
			for(int k = i+1;k <= j;k++){
				bons.push_back(t);
				mark[t] = 1;
				t += v[k];
			}
			int res = 0;
			dp[r+1][r+1][1] = max(dp[r+1][r+1][1], dp[l][r][0]);
			t -= v[r+1];
			for(int k = j+2;k <= n;k++){
				if(t >= 0 and mark[t] == 1){
					res++;
				}
				t -= v[k];
				dp[r+1][k][1] = max(dp[r+1][k][1], dp[l][r][0]+res);
			}
			for(auto x : bons){
				mark[x] = 0;
			}
			bons.clear();
			//
			t = 0;
			t += v[r];
			for(int k = r-1;k >= i;k--){
				bons.push_back(t);
				mark[t] = 1;
				t += v[k];
			}
			if(debug and l == 3 and r == 4){
				for(auto x : bons){
					cout << x << ' ';
				}
				cout << endl;
			}
			res = 0;
			t = v[r+1];
			if(debug and l == 3 and r == 4) cout << t << ' ';
			dp[r+1][r+1][0] = max(dp[r+1][r+1][0], dp[l][r][1] + res);
			for(int k = r+2;k <= n;k++){
				if(t < N*N and mark[t] == 1){
					res++;
				}
				t += v[k];
				if(debug and l == 3 and r == 4 and k == 6){
					cout << res << endl;
				}
				dp[r+1][k][0] = max(dp[r+1][k][0], dp[l][r][1]+res);
			}
			for(auto x : bons) mark[x] = 0;
				bons.clear();
		}
	}
	int res = 0;
	for(int i = 0;i <= n;i++){
		res = max(res, dp[i][n][0]);
		res = max(res, dp[i][n][1]);
	}
	cout << res << endl;
	return 0;
}

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