Submission #1003614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003614		Lalic	Cigle (COI21_cigle)	C++17	0 / 100	3 ms	5468 KiB

cigle

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

const int MAXN = 5005;

int dp[MAXN][MAXN], pref[MAXN][MAXN];

void solve(){
	int n; cin >> n;
	
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++) cin >> arr[i];
	
	vector<int> ps(n+1); ps[0]=0;
	for(int i=1;i<=n;i++) ps[i]+=ps[i-1]+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>0 && 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: 0 / 9
• Subtask 2: 0 / 11
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 52