Submission #706649

#	Time	Username	Problem	Language	Result	Execution time	Memory
706649		ld_minh4354	Cigle (COI21_cigle)	C++17	100 / 100	251 ms	392708 KiB

cigle

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define debug(x) cout<<#x<<": "<<x<<"\n"



signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//	freopen("input.000","r",stdin);
//	freopen("output.000","w",stdout);
//	srand((unsigned)time(NULL));
//	rand()
	
	int n,i,a[5005],dp[5005][5005],j,cnt,l,diff,optl,ans,dpmax[5005][5005];
	
	cin>>n;
	for (i=1;i<n+1;i++) cin>>a[i];
	
	for (j=1;j<n+1;j++) dp[0][j]=dp[1][j]=0;
	for (j=1;j<n+1;j++) dpmax[0][j]=dpmax[1][j]=0;
	
	ans=0;
	for (i=2;i<n;i++)
	{
		cnt=0;l=i-1;diff=0;optl=i-1;
		
		dp[i][i+1]=dpmax[i-1][i];
		dpmax[i][i+1]=max(dpmax[i-1][i+1],dp[i][i+1]);
		
		for (j=i+2;j<n+1;j++)
		{
			diff -= a[j-1];
			while (diff<0 and l>0)
			{
				diff += a[l+1];
				l--;
			}
			
			if (diff==0)
			{
				cnt++;
				optl=l;
			}
			
			dp[i][j]=max(dp[i][j-1],dpmax[optl][i]+cnt);
			dpmax[i][j]=max(dpmax[i-1][j],dp[i][j]);
			
			ans=max(ans,dp[i][j]);
//			cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<optl<<" "<<cnt<<"\n";
		}
	}
	
	cout<<ans;
}

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