제출 #395817

#제출 시각아이디문제언어결과실행 시간메모리
395817Pichon5Global Warming (CEOI18_glo)C++17
0 / 100
124 ms3336 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(); //j+1 es el tamaño del lis que termina en v[i] dp[j] = temps[i]; pref_longest[i] = j + 1;//el lis que termina en i 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); //cout<<"pos "<<pos<<" + "<<pref_longest[i]<<endl; 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...