Submission #1003621

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003621		Lalic	Cigle (COI21_cigle)	C++17	100 / 100	331 ms	196688 KiB

cigle

#include <bits/stdc++.h>
#pragma GCC optimize "Ofast,unroll-loops"
#pragma GCC target "avx2"
using namespace std;

const int MAXN = 5005;

void solve(){
	int n; cin >> n;
	
	vector<vector<int>> dp(n+1, vector<int>(n+1, 0)), pref(n+1, vector<int>(n+1, 0));
	
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++) cin >> arr[i];
	
	for(int l=2;l<=n;l++){
		int ptr=l-1, sum=0, curr=0, tot=0;
		for(int r=l;r<=n;r++){
			dp[l][r]=max(dp[l][r-1], pref[ptr][l-1]+tot);
			sum+=arr[r];
			while(ptr>1 && curr<sum) curr+=arr[ptr--];
			tot+=(curr==sum);
		}
		
		pref[0][l]=dp[0][l];
		for(int i=1;i<=l;i++) pref[i][l]=max(dp[i][l], pref[i-1][l]);
	}
	
	int ans=pref[n][n];
	cout << ans << "\n";
}


int32_t main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int tt=1;
	//~ cin >> tt;
	while(tt--) solve();
	return 0;
}

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