# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
314069 | 2020-10-18T06:59:58 Z | tushar_2658 | Global Warming (CEOI18_glo) | C++14 | 72 ms | 3448 KB |
#include "bits/stdc++.h" using namespace std; const int maxn = 200005; int a[maxn], x; int n; int main(int argc, char const *argv[]) { scanf("%d %d", &n, &x); for(int i = 1; i <= n; ++i){ scanf("%d", &a[i]); } vector<int> dp(n + 1, 1e8); dp[0] = -1e8; vector<int> L(n + 1); for(int i = 1; i <= n; ++i){ int idx = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); dp[idx] = a[i]; L[i] = idx; } vector<int> dp1(n + 1, 1e8); dp1[0] = -1e8; int ans = 0; for(int i = n; i >= 1; --i){ int idx = lower_bound(dp1.begin(), dp1.end(), -a[i]) - dp1.begin(); int idx1 = lower_bound(dp1.begin(), dp1.end(), -a[i] + x) - dp1.begin(); dp1[idx] = -a[i]; ans = max(ans, L[i] + idx1 - 1); } cout << ans << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 256 KB | Output is correct |
13 | Correct | 1 ms | 256 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 256 KB | Output is correct |
16 | Correct | 1 ms | 256 KB | Output is correct |
17 | Correct | 1 ms | 256 KB | Output is correct |
18 | Correct | 1 ms | 288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 256 KB | Output is correct |
13 | Correct | 1 ms | 256 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 256 KB | Output is correct |
16 | Correct | 1 ms | 256 KB | Output is correct |
17 | Correct | 1 ms | 256 KB | Output is correct |
18 | Correct | 1 ms | 288 KB | Output is correct |
19 | Incorrect | 1 ms | 384 KB | Output isn't correct |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 72 ms | 3448 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 1152 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 2040 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 256 KB | Output is correct |
5 | Correct | 1 ms | 256 KB | Output is correct |
6 | Correct | 1 ms | 256 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 256 KB | Output is correct |
9 | Correct | 1 ms | 256 KB | Output is correct |
10 | Correct | 1 ms | 256 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 256 KB | Output is correct |
13 | Correct | 1 ms | 256 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 0 ms | 256 KB | Output is correct |
16 | Correct | 1 ms | 256 KB | Output is correct |
17 | Correct | 1 ms | 256 KB | Output is correct |
18 | Correct | 1 ms | 288 KB | Output is correct |
19 | Incorrect | 1 ms | 384 KB | Output isn't correct |
20 | Halted | 0 ms | 0 KB | - |