Submission #384052

#TimeUsernameProblemLanguageResultExecution timeMemory
384052iulia13Global Warming (CEOI18_glo)C++14
100 / 100
115 ms4204 KiB
#include <iostream> using namespace std; const int nmax = 2e5 + 5; int dp[nmax]; int dp2[nmax]; int v[nmax]; int a[nmax]; int bs(int st, int dr, int val, int a[]) { int x = 0; while (st <= dr) { int mid = (st + dr) / 2; if (a[mid] < val) { x = mid; st = mid + 1; } else dr = mid - 1; } return x; } int main() { int n, x, i, l = 0, ans = 0; cin >> n >> x; for (i = 1; i <= n; i++) cin >> v[i]; for (i = n; i; i--) { int poz = bs(1, l, -v[i], a); dp[i] = poz + 1; if (poz == l) l++; a[poz + 1] = -v[i]; ans = max(ans, dp[i]); } l = 0; for (i = 1; i <= n; i++) { int poz = bs(1, l, (v[i] + x), a); ans = max(ans, dp[i] + poz); poz = bs(1, l, v[i], a); if (poz == l) l++; a[poz + 1] = v[i]; } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...