| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 702017 | ld_minh4354 | Financial Report (JOI21_financial) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
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 (X<=m) l->update(X,V);
else r->update(X,V);
val=max(l->val,r->val);
}
}
int query(int S,int E)
{
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(1ll,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;
}