Submission #706626

#	Time	Username	Problem	Language	Result	Execution time	Memory
706626		ld_minh4354	Cigle (COI21_cigle)	C++17	0 / 100	1 ms	340 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];
	
	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 (i=0;i<n+1;i++) dpmax[i]=0;
	
	ans=0;
	for (i=2;i<n;i++)
	{
		cnt=0;l=i-2;diff=a[i];optl=i-1;
		
		dp[i][i+1]=dpmax[i-1];
		dpmax[i+1]=max(dpmax[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]=cnt+dpmax[optl];
			ans=max(ans,dp[i][j]);
			dpmax[i]=max(dpmax[i],dp[i][j]);
//			cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<optl<<" "<<cnt<<"\n";
		}
	}
	
	cout<<ans;
}

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