Submission #328364

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
328364	2020-11-16T09:55:15 Z	Karen124	Global Warming (CEOI18_glo)	C++14	28 / 100	4 ms	748 KB

glo

#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long int 
#define F first
#define S second
#define pb push_back
#define md ((b + e) >> 1)
#define lc (ind << 1)
#define rc (lc | 1)

const ll N = 5000 + 10;
const ll M = 50;
const ll MOD = 1e9 + 7;
const ll INF = 1e9 + 10;
int n, X, a[N], l[N], r[N], f[N], ans;
int main() {
    cin >> n >> X;
    int len = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        int p = lower_bound(l, l + len, a[i]) - l;
        l[p] = a[i];
        len = max(len, p + 1);
        f[i] = p + 1;
    }
    ans = f[n - 1];
    len = 0;
    for (int i = n - 1; i >= 0; i--){
        a[i] *= -1;
        int p = upper_bound(r, r + len, a[i] - 1) - r;
        ans = max(ans, f[i] + p);
        a[i] -= X;
        p = lower_bound(r, r + len, a[i]) - r;
        r[p] = a[i];
        len = max(len, p + 1);
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct

Subtask #3

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct

Subtask #4

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Correct	1 ms	364 KB	Output is correct
17	Correct	1 ms	384 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	384 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	1 ms	364 KB	Output is correct
26	Correct	1 ms	364 KB	Output is correct
27	Runtime error	4 ms	748 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
28	Halted	0 ms	0 KB	-