# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1111161 | Ghulam_Junaid | Global Warming (CEOI18_glo) | C++17 | 87 ms | 5448 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int inf = 2e9 + 10;
int main(){
int n, x;
cin >> n >> x;
int a[n];
for (int i=0; i<n; i++)
cin >> a[i];
int ans = 0;
int pref[n] = {0};
int suf[n] = {0};
int dp[n + 1];
for (int i = 1; i <= n; i ++)
dp[i] = inf;
dp[0] = -inf;
for (int i = n - 1; i >= 0; i --){
int lb = lower_bound(dp, dp + n + 1, -a[i]) - dp;
suf[i] = lb;
int ub = lower_bound(dp, dp + n + 1, -(a[i] + x)) - dp;
dp[ub] = -(a[i] + x);
}
for (int i = 1; i <= n; i ++)
dp[i] = inf;
dp[0] = -inf;
for (int i = 0; i < n; i ++){
int ub = lower_bound(dp, dp + n + 1, a[i]) - dp;
dp[ub] = a[i];
ans = max(ans, ub + suf[i] - 1);
}
cout << ans << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |