Submission #503893

#	Time	Username	Problem	Language	Result	Execution time	Memory
503893		Ai7081	Global Warming (CEOI18_glo)	C++17	25 / 100	2081 ms	2888 KiB

glo

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

int n, x, a[N], out;
vector<int> dp;

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

    cin >> n >> x;
    for (int i=1; i<=n; i++) cin >> a[i];

    if (x==0) {
        for (int i=1; i<=n; i++) {
            auto idx = lower_bound(dp.begin(), dp.end(), a[i]);
            if (idx == dp.end()) dp.push_back(a[i]);
            else *idx = a[i];
        }
        cout << dp.size();
        return 0;
    }

    for (int c=-x; c<=x; c++) {
        for (int i=1; i<=n; i++) {
            for (int j=i; j<=n; j++) {
                dp.clear();
                for (int k=1; k<=n; k++) {
                    int now;
                    now = (i<=k && k<=j) ? a[k]+c : a[k];
                    auto idx = lower_bound(dp.begin(), dp.end(), now);
                    if (idx == dp.end()) dp.push_back(now);
                    else *idx = now;
                }
                out = max(out, (int)dp.size());
            }
        }
    }
    cout << out;

    return 0;
}

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