Submission #702049

#	Time	Username	Problem	Language	Result	Execution time	Memory
702049		ld_minh4354	Financial Report (JOI21_financial)	C++14	28 / 100	4105 ms	779348 KiB

Main

#include<bits/stdc++.h>
using namespace std;
 
#define int long long
#define fi first
#define se second
#define pb push_back
 
 
 
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,d,i,a[7005],dp[7005][7005],ans,j,k,u,min_dist,c;
	
	cin>>n>>d;
	for (i=1;i<n+1;i++) cin>>a[i];
	
	if (n==1)
	{
		cout<<1;return 0;
	}
	
	if (a[1]<a[2]) dp[2][1]=2;else dp[2][1]=1;
	
	for (j=1;j<n;j++) for (i=j+1;i<n+1;i++)
	{
		c=0;min_dist=0;
		for (k=j+1;k<i;k++) if (a[k]>a[j])
		{
			c++;
			min_dist=max(min_dist,c);
		}
		else c=0;
		
		if (min_dist<d)
		{
			dp[i][j]=1;
			
			for (k=1;k<d+1;k++)
			if (i-k>j)
			{
				if (a[j]>=a[i-k]) dp[i][j]=max(dp[i][j],dp[i-k][j]);
			}
			else if (i-k==j)
			{
				for (u=1;u<j;u++) if (a[u]<a[j]) dp[i][j]=max(dp[i][j],dp[j][u]);
			}
		
			if (a[i]>a[j]) dp[i][j]++;
		}
		else dp[i][j]=-1;
	}
	
//	for (i=1;i<n+1;i++)
//	{
//		for (j=0;j<i;j++) cout<<dp[i][j]<<" ";
//		cout<<"\n";
//	}
	
	ans=1;
	for (j=1;j<n;j++) ans=max(ans,dp[n][j]);
	cout<<ans;
}
 

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35