# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
260697 | 2020-08-10T18:22:12 Z | bigg | Global Warming (CEOI18_glo) | C++14 | 2000 ms | 7032 KB |
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 10; const ll INF =1e18; ll dp[MAXN], v[MAXN], neg[MAXN]; int ans1[MAXN]; int main(){ int n; ll x; scanf("%d %lld", &n, &x); for(int i = 1; i <= n; i++) scanf("%lld", &v[i]), dp[i] = INF, neg[i] = -v[i]; //dp[0] = INF; int ans = -1; for(int i = 0; i <= n; i++) dp[i] = INF; for(int i = 1; i <= n; i++){ int it1 = lower_bound(dp, dp + n, v[i]) - dp; dp[it1] = v[i]; ans1[i] = it1 +1; ans = max(ans, it1 + 1); } for(int k = -x; k <= x; k++){ for(int i = 0; i <= n; i++) dp[i] = INF; for(int i = n; i; i--){ int it1 = lower_bound(dp, dp + n, neg[i] +k) - dp; int it2 = lower_bound(dp, dp + n, neg[i]) - dp; dp[it2] = neg[i]; ans = max(ans, it1 + ans1[i]); //printf("%\n"); } } printf("%d\n",ans ); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 360 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 360 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 360 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 0 ms | 384 KB | Output is correct |
19 | Execution timed out | 2078 ms | 384 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 83 ms | 7008 KB | Output is correct |
2 | Correct | 86 ms | 7028 KB | Output is correct |
3 | Correct | 80 ms | 7032 KB | Output is correct |
4 | Correct | 83 ms | 7020 KB | Output is correct |
5 | Correct | 64 ms | 6904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 2184 KB | Output is correct |
2 | Correct | 69 ms | 2176 KB | Output is correct |
3 | Correct | 72 ms | 2176 KB | Output is correct |
4 | Correct | 64 ms | 2040 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 66 ms | 1920 KB | Output is correct |
7 | Correct | 54 ms | 2176 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2079 ms | 3980 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 0 ms | 384 KB | Output is correct |
4 | Correct | 1 ms | 360 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 0 ms | 384 KB | Output is correct |
9 | Correct | 0 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Correct | 1 ms | 384 KB | Output is correct |
15 | Correct | 1 ms | 384 KB | Output is correct |
16 | Correct | 1 ms | 384 KB | Output is correct |
17 | Correct | 0 ms | 384 KB | Output is correct |
18 | Correct | 0 ms | 384 KB | Output is correct |
19 | Execution timed out | 2078 ms | 384 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |