# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
259882 | 2020-08-08T18:45:47 Z | peuch | Global Warming (CEOI18_glo) | C++17 | 77 ms | 2680 KB |
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; const int INF = 2e9 + 7; int n, x; int v[MAXN]; int dp[MAXN]; int maxi[MAXN]; int ans; int main(){ scanf("%d %d", &n, &x); for(int i = 1; i <= n; i++) scanf("%d", &v[i]); for(int j = 1; j <= n; j++) dp[j] = INF; for(int i = 1; i <= n; i++){ int k = lower_bound(dp, dp + 1 + n, v[i]) - dp; dp[k] = v[i]; maxi[i] = max(maxi[i - 1], k); } for(int j = 1; j <= n; j++) dp[j] = INF; dp[0] = -INF; for(int i = n; i > 0; i--){ int aux = lower_bound(dp, dp + 1 + n, -v[i]) - dp; aux--; int k = lower_bound(dp, dp + 1 + n, -v[i] - x) - dp; dp[k] = -v[i] - x; ans = max(ans, maxi[i] + aux); } printf("%d\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 77 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 20 ms | 896 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 35 ms | 1536 KB | Output is correct |
2 | Correct | 35 ms | 1528 KB | Output is correct |
3 | Correct | 75 ms | 2680 KB | Output is correct |
4 | Correct | 67 ms | 2680 KB | Output is correct |
5 | Correct | 31 ms | 1536 KB | Output is correct |
6 | Correct | 49 ms | 2552 KB | Output is correct |
7 | Correct | 54 ms | 2552 KB | Output is correct |
8 | Correct | 30 ms | 1528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |