Submission #1165707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165707		altern23	Global Warming (CEOI18_glo)	C++20	10 / 100	561 ms	3816 KiB

glo

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;


int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, x; cin >> n >> x;
        vector<ll> a(n + 5);
        for(int i = 1; i <= n; i++) cin >> a[i];

        auto f = [&](ll idx){
            vector<ll> cur;
            for(int j = 1; j <= n; j++){
                ll val = a[j] - (idx >= j ? x : 0);
                if(cur.empty() || cur.back() < val){
                    cur.push_back(val);
                }
                else{
                    ll pt = lower_bound(cur.begin(), cur.end(), val) - cur.begin();
                    if(pt != cur.size()) cur[pt] = val;
                }
            }
            return (ll)cur.size();
        };

        // for(int i = 1; i <= n; i++) cout << f(i) << " \n"[i == n];
        
        ll lf = 0, rg = n;
        for(;rg - lf > 2;){
            ll mid1 = lf + (rg - lf) / 3;
            ll mid2 = rg - (rg - lf) / 3;
            if(f(mid1) < f(mid2)){
                lf = mid1;
            }
            else rg = mid2;
        }

        ll ans = -INF;
        for(int i = lf; i <= rg; i++){
            ans = max(ans, f(i));
        }

        cout << ans << "\n";
    }   
}

/*

*/ 

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