Submission #1165708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165708		altern23	Global Warming (CEOI18_glo)	C++20	28 / 100	2096 ms	1864 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();
        };

        ll ans = -INF;
        for(int i = 1; i <= n; i++) ans = max(ans, f(i));

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

/*

*/ 

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