제출 #993476

#제출 시각아이디문제언어결과실행 시간메모리
993476messiuuuuuGlobal Warming (CEOI18_glo)C++14
100 / 100
75 ms5484 KiB
#include <bits/stdc++.h> using namespace std; int temps[200005]; int pref_longest[200005]; int main() { int n; int x; cin >> n >> x; for (int i = 0; i < n; i++) { cin >> temps[i]; } vector<int> dp(n, INT_MAX); int longest = 0; // longest increasing subsequence ending at i for (int i = 0; i < n; i++) { int j = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin(); dp[j] = temps[i]; pref_longest[i] = j + 1; longest = max(longest, pref_longest[i]); } dp = vector<int>(n, INT_MAX); // longest decreasing subsequence ending at i of reverse // = longest increasing subsequence starting at i 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); int insert_pos = lower_bound(dp.begin(), dp.end(), -temps[i]) - dp.begin(); dp[insert_pos] = -temps[i]; } cout << longest << endl; }
#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...