Submission #1103979

#TimeUsernameProblemLanguageResultExecution timeMemory
1103979vjudge1Global Warming (CEOI18_glo)C++17
100 / 100
39 ms4688 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int a[200200], dp[200200], l[202100]; void solve() { int n, k; cin >> n >> k; int cnt = 0; for (int i = 1;i <= n;i++) { cin >> a[i]; int idx = lower_bound(dp, dp + cnt, a[i]) - dp; if (idx == cnt) cnt++; dp[idx] = a[i]; l[i] = idx + 1; } int mx = cnt; cnt = 0; for (int i = n;i >= 1;i--) { int idx = lower_bound(dp, dp + cnt, -a[i]) - dp; mx = max(mx, l[i] + idx); idx = lower_bound(dp, dp + cnt, -(a[i] + k)) - dp; if (idx == cnt) cnt++; dp[idx] = -(a[i] + k); } cout << mx << '\n'; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int q = 1; while (q--) { solve(); } 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...