Submission #1259567

#TimeUsernameProblemLanguageResultExecution timeMemory
1259567vk3601hGlobal Warming (CEOI18_glo)C++20
100 / 100
40 ms3532 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n, x; cin >> n >> x; vector<int> temps(n); for (int i = 0; i < n; ++i) cin >> temps[i]; int longest = 0; vector<int> dp(n, INT_MAX); vector<int> pref_longest(n); for (int i = 0; i < n; ++i){ int pos = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin(); dp[pos] = temps[i]; pref_longest[i] = pos + 1; longest = max(longest, pref_longest[i]); } dp = vector<int> (n, INT_MAX); for (int i = n - 1; i >= 0; --i){ int pos = lower_bound(dp.begin(), dp.end(), -temps[i] + x) - dp.begin(); longest = max(longest, pref_longest[i] + pos); pos = lower_bound(dp.begin(), dp.end(), -temps[i]) - dp.begin(); dp[pos] = -temps[i]; } cout << longest; 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...