Submission #1307852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307852		comet0	Global Warming (CEOI18_glo)	C++20	28 / 100	2096 ms	6620 KiB

glo

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x; cin >> n >> x;
    vector<ll> a(n); for (auto& v : a) cin >> v;

    vector<int> b(n, 1);
    vector<pair<int, ll>> c(n, {1, LLONG_MIN});
    vector<int> d(n, 0);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                b[i] = max(b[i], b[j] + 1);
            }

            if (a[j] < a[i] + x) {
                int k = b[j] + 1;
                ll l = a[j] - a[i];
                if (k > c[i].first ||
                    (k == c[i].first && l < c[i].second)) {
                    c[i] = {k, l};
                }
            }
            if (a[j] < a[i]) {
                int k = c[j].first + 1;
                ll l = c[j].second;
                if (k > c[i].first ||
                    (k == c[i].first && l < c[i].second)) {
                    c[i] = {k, l};
                }
            }

            ll m = c[j].second;
            ll u = a[i] - a[j];
            if (m < u && m < x && u > -x) {
                d[i] = max(d[i], c[j].first + 1);
            }

            if (a[j] < a[i] && d[j] > 0) {
                d[i] = max(d[i], d[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max({ans, b[i], c[i].first, d[i]});
    }
    cout << ans;
}

• 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