Submission #483422

#	Time	Username	Problem	Language	Result	Execution time	Memory
483422		keertan	Global Warming (CEOI18_glo)	C++17	100 / 100	46 ms	2640 KiB

glo

/**
 * If you live in imaginary world when your imaginary situation encounter in 
 * real situation you can't enjoiy it because you have to do pending work.
 * {This pending work appeared because you wasted that time for your useless
 * imagianry thinking.}
 */
#include<bits/stdc++.h>
using namespace std;
//#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
#define sz(x) (int32_t)(x.size())
const int N=1e2;


void solve(){
    int n,m;
    cin>>n>>m;
    vector<int> z(n);
    for (int &it:z){cin>>it;}
    vector<int> dp;
    int pref[n];
    for (int i=0;i<n;i++){
        int pos=lower_bound(all(dp),z[i])-dp.begin();
        pref[i]=pos+1;
        if (pos==sz(dp)){
            dp.push_back(z[i]);
        }
        else{
            dp[pos]=z[i];
        }
    }
    dp.clear();
    int ans=0;
    for (int i=n-1;~i;i--){
        int pos=lower_bound(all(dp),-z[i]+m)-dp.begin();
        ans=max(ans,pref[i]+pos);
        pos=lower_bound(all(dp),-z[i])-dp.begin();
        if (pos==sz(dp)){
            dp.push_back(-z[i]);
        }
        else{
            dp[pos]=-z[i];
        }
    }
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tq=1;
    //cin>>tq;
    for (;tq;tq--){solve();}
}
//is a bruteforce possible?
//think greedier, make more assumptions
// if we you find solution using loop to decrease complexity use bs
//stuck for more than 5 minutes? move on 

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25