Submission #771181

#	Time	Username	Problem	Language	Result	Execution time	Memory
771181		gagik_2007	Financial Report (JOI21_financial)	C++17	65 / 100	4024 ms	7156 KiB

Main

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=3e5+7;
ll n,m,k;
ll a[N];
ll dp[N];
int ri[N];

void precalc() {
    
}

int main() {
    precalc();
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    if(k==1){
        stack<int>st;
        ll ans=0;
        for(int i=n-1;i>=0;i--){
            while(!st.empty()&&st.top()<=a[i]){
                st.pop();
            }
            st.push(a[i]);
            ans=max(ans,(ll)st.size());
        }
        cout<<ans<<endl;
        return 0;
    }
    if(k==n){
        vector<int>d;
        for(int i=0;i<n;i++){
            auto it=lower_bound(d.begin(),d.end(),a[i]);
            if(it==d.end()){
                d.push_back(a[i]);
            }
            else{
                d[it-d.begin()]=a[i];
            }
        }
        cout<<d.size()<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        ri[i]=i;
        for(int j=i+1;j<min(n,ri[i]+k+1);j++){
            if(a[j]<=a[i]){
                ri[i]=j;
            }
        }
        //cout<<ri[i]<<" ";
    }
    //cout<<endl;
    ll ans=0;
    for(int i=0;i<n;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(a[i]>a[j]&&ri[j]>=i-k){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        if(ri[i]==n-1){
            ans=max(ans,dp[i]);
        }
        //cout<<dp[i]<<" ";
    }
    cout<<ans<<endl;
}

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