Submission #503893

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
503893	2022-01-09T06:37:06 Z	Ai7081	Global Warming (CEOI18_glo)	C++17	25 / 100	2000 ms	2888 KB

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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	216 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	320 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	216 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	320 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	16 ms	320 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	57 ms	204 KB	Output is correct
15	Correct	23 ms	320 KB	Output is correct
16	Correct	24 ms	320 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	324 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	216 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	320 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	16 ms	320 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	57 ms	204 KB	Output is correct
15	Correct	23 ms	320 KB	Output is correct
16	Correct	24 ms	320 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	324 KB	Output is correct
19	Execution timed out	2076 ms	332 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #4

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	2244 KB	Output is correct
2	Correct	30 ms	2348 KB	Output is correct
3	Correct	34 ms	2344 KB	Output is correct
4	Correct	31 ms	2364 KB	Output is correct
5	Correct	19 ms	2888 KB	Output is correct

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2081 ms	988 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2073 ms	1608 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	324 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	216 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	320 KB	Output is correct
10	Correct	1 ms	328 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	16 ms	320 KB	Output is correct
13	Correct	0 ms	204 KB	Output is correct
14	Correct	57 ms	204 KB	Output is correct
15	Correct	23 ms	320 KB	Output is correct
16	Correct	24 ms	320 KB	Output is correct
17	Correct	1 ms	204 KB	Output is correct
18	Correct	1 ms	324 KB	Output is correct
19	Execution timed out	2076 ms	332 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-