제출 #1278062

#제출 시각아이디문제언어결과실행 시간메모리
1278062tagizadeGlobal Warming (CEOI18_glo)C++17
100 / 100
48 ms4364 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; ll x; if (!(cin >> n >> x)) return 0; vector<ll> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; vector<int> pref(n); const ll INF = (ll)9e18; vector<ll> dp(n, INF); int ans = 0; for (int i = 0; i < n; ++i) { int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); dp[pos] = a[i]; pref[i] = pos + 1; ans = max(ans, pref[i]); } fill(dp.begin(), dp.end(), INF); for (int i = n - 1; i >= 0; --i) { int pos = lower_bound(dp.begin(), dp.end(), -a[i] + x) - dp.begin(); ans = max(ans, pref[i] + pos); int ins = lower_bound(dp.begin(), dp.end(), -a[i]) - dp.begin(); dp[ins] = -a[i]; } cout << ans << '\n'; 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...