# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
314068 | 2020-10-18T06:58:37 Z | tushar_2658 | Global Warming (CEOI18_glo) | C++14 | 70 ms | 5368 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 = 1; i <= n; ++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[n - i + 1] + 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 | Incorrect | 0 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Incorrect | 0 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 256 KB | Output is correct |
2 | Incorrect | 0 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 70 ms | 5368 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 1536 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 38 ms | 2816 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 | Incorrect | 0 ms | 256 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |