oj.uz

Submission #706631

# Submission time Handle Problem Language Result Execution time Memory
706631 2023-03-07T08:40:28 Z ld_minh4354 Cigle (COI21_cigle) C++17
0 / 100
 75 ms 196440 KB 
#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+dp[optl][i];
			dp[i][j]=max(dp[i][j],dp[i][j-1]);
			
			ans=max(ans,dp[i][j]);
//			cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<optl<<" "<<cnt<<"\n";
		}
	}
	
	cout<<ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196344 KB Output is correct
2 Correct 73 ms 196436 KB Output is correct
3 Incorrect 75 ms 196440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196344 KB Output is correct
2 Correct 73 ms 196436 KB Output is correct
3 Incorrect 75 ms 196440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 196364 KB Output is correct
2 Incorrect 75 ms 196436 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196344 KB Output is correct
2 Correct 73 ms 196436 KB Output is correct
3 Incorrect 75 ms 196440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 196344 KB Output is correct
2 Correct 73 ms 196436 KB Output is correct
3 Incorrect 75 ms 196440 KB Output isn't correct
4 Halted 0 ms 0 KB -