Submission #1002883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002883		Lobo	Cigle (COI21_cigle)	C++17	20 / 100	1033 ms	2476 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 j = 1; j <= n; j++) {
		for(int i = 1; i <= j; i++) {
			set<int> sij;
			int sum = 0;
			for(int x = i; x < j; x++) {
				sum+= a[x];
				sij.insert(sum);
			}
			for(int k = 1; k <= i-1; k++) {
				int sm = 0;
				int qtd = 0;
				for(int x = i-1; x > k; x--) {
					sm+= a[x];
					if(sij.count(sm)) qtd++;
				}
				dp[i][j] = max(dp[i][j],dp[k][i-1]+qtd);
			}
		}
	}

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

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