Submission #1000520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000520		niwrad	Global Warming (CEOI18_glo)	C++17	100 / 100	109 ms	6260 KiB

glo

#include <bits/stdc++.h>

using namespace std;
int inf = 2e9 + 7;


int main() {
    int n, x;
    cin >> n >> x;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    vector<int> suff_dp(n + 1, -inf);
    suff_dp[0] = inf;
    vector<pair<int, int>> steps(n, {-1, -1});
    for (int i = n - 1; i >= 0; i--) {
        int l = (int) (upper_bound(suff_dp.begin(), suff_dp.end(), vec[i] + x, greater_equal<int>()) - suff_dp.begin());
        if (suff_dp[l] < vec[i] + x) {
            steps[i] = {l, suff_dp[l]};
            suff_dp[l] = vec[i] + x;
        }
    }
    int max = 0;
    for (int i = 0; i <= n; i++) {
        if (suff_dp[i] != -inf) {
            max = i;
        }
    }
    vector<int> pref_dp(n + 1, inf);
    pref_dp[0] = -inf;
    for (int i = 0; i < n; i++) {
        int s = -1;
        if (steps[i].first != -1) {
            s = steps[i].first;
            suff_dp[steps[i].first] = steps[i].second;
        }
        int l = (int) (upper_bound(pref_dp.begin(), pref_dp.end(), vec[i]) - pref_dp.begin());
        if (pref_dp[l - 1] < vec[i] && vec[i] < pref_dp[l]) {
            pref_dp[l] = vec[i];
            int p = (int) (lower_bound(suff_dp.begin(), suff_dp.end(), vec[i], greater<int>()) - suff_dp.begin());
            l += p - 1;
            max = std::max(max, l);
        }
        if (s != -1) {
            int p = (int) (lower_bound(pref_dp.begin(), pref_dp.end(), suff_dp[s]) - pref_dp.begin());
            max = std::max(max, s + p - 1);
        }
    }
    cout << max << "\n";
}

• 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