Submission #398997

#	Time	Username	Problem	Language	Result	Execution time	Memory
398997		KoD	Global Warming (CEOI18_glo)	C++17	100 / 100	67 ms	4596 KiB

glo

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

constexpr int INF = std::numeric_limits<int>::max() / 2;

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, X;
    std::cin >> N >> X;
    Vec<int> A(N);
    for (auto& x: A) {
        std::cin >> x;
    }    
    Vec<int> up(N + 1, INF), down(N + 1, INF);
    up[0] = down[0] = -INF;
    for (const auto x: A) {
        const int u = std::lower_bound(up.begin(), up.end(), x) - up.begin();
        const int d = std::lower_bound(down.begin(), down.end(), x) - down.begin();
        up[u] = x;
        down[d] = x;
        down[u] = std::min(down[u], x - X);
    }
    std::cout << std::lower_bound(down.begin(), down.end(), INF) - down.begin() - 1 << '\n';
    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