Submission #702026

#	Time	Username	Problem	Language	Result	Execution time	Memory
702026		ld_minh4354	Financial Report (JOI21_financial)	C++14	0 / 100	293 ms	391344 KiB

Main

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

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

struct node
{
	int s,e,m,val;
	node *l,*r;
	
	node(int S,int E)
	{
		s=S;e=E;m=(s+e)/2;
		val=-1;
		l=nullptr;r=nullptr;
	}
	
	void create()
	{
		if (s!=e)
		{
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void update(int X,int V)
	{
		if (s==e and s==X) val=V;
		else
		{
			if (l==nullptr) create();
			if (X<=m) l->update(X,V);
			else r->update(X,V);
			val=max(l->val,r->val);
		}
	}
	
	int query(int S,int E)
	{
		if (l==nullptr) return -1;
		if (s==S and e==E) return val;
		else if (E<=m) return l->query(S,E);
		else if (S>=m+1) return r->query(S,E);
		else return max(l->query(S,m),r->query(m+1,E));
	}
} *root[7005];

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,min_dist,c,pre1,pre2[7005];
	
	cin>>n>>d;
	for (i=1;i<n+1;i++) cin>>a[i];
	
	if (n==1)
	{
		cout<<1;return 0;
	}
	
	for (i=1;i<n+1;i++) root[i]=new node(1,n);
	for (i=1;i<n+1;i++) pre2[i]=-1;
	
	if (a[1]<a[2]) dp[2][1]=2;else dp[2][1]=1;
	
	
	
	if (a[1]>=a[2]) root[1]->update(2,dp[2][1]); else pre2[2]=dp[2][1];
	
	for (i=3;i<n+1;i++) for (j=1;j<i;j++)
	{
		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)
		{
			pre1=root[j]->query(max(j,i-d), i-1);
			dp[i][j]=max(1,pre1);
			
			if (i-j<=d) dp[i][j]=max(dp[i][j], pre2[j]);
		
			if (a[i]>a[j]) dp[i][j]++;
		}
		else dp[i][j]=-1;
		
		if (a[j]>=a[i]) root[j]->update(i,dp[i][j]); //pre1[j]=max(pre1[j], dp[i][j]);
		else pre2[i]=max(pre2[i], dp[i][j]);
	}
	
//	for (i=2;i<n+1;i++)
//	{
//		for (j=1;j<i;j++) cout<<dp[i][j]<<" ";
//		cout<<"\n";
//	}
	
//	for (i=1;i<n+1;i++) debug(pre1[i]);
//	for (i=1;i<n+1;i++) debug(pre2[i]);
	
	ans=1;
	for (j=1;j<n;j++) ans=max(ans,dp[n][j]);
	cout<<ans;
}

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