Submission #1175926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175926		KindaNameless	Global Warming (CEOI18_glo)	C++20	100 / 100	37 ms	3012 KiB

glo

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

#define ll long long
#define ld long double

void solve() {
    int N, x; cin >> N >> x;

    int answer = 1;
    vector<int> P, S;
    vector<int> t(N), dp(N);
    for(int i = 0; i < N; ++i) {
        cin >> t[i];

        auto pos = lower_bound(P.begin(), P.end(), t[i]);
        dp[i] = pos - P.begin() + 1;
        answer = max(answer, dp[i]);
        if(pos == P.end()) {
            P.push_back(t[i]);
        }
        else {
            P[pos - P.begin()] = t[i];
        }
    }

    for(int i = N - 1; i >= 0; --i) {
        auto pos = lower_bound(S.begin(), S.end(), -t[i] + x);
        int len = pos - S.begin();
        answer = max(answer, dp[i] + len);

        pos = lower_bound(S.begin(), S.end(), -t[i]);
        if(pos == S.end()) {
            S.push_back(-t[i]);
        }
        else {
            S[pos - S.begin()] = -t[i];
        }
    }

    cout << answer;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1; //cin >> tc;

    while(tc--) {
        solve();
    }

    return 0;
}

• 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