제출 #957072

#제출 시각아이디문제언어결과실행 시간메모리
957072Charizard2021Global Warming (CEOI18_glo)C++17
100 / 100
92 ms4624 KiB
#include<bits/stdc++.h> using namespace std; int main(){ int n, x; cin >> n >> x; int a[n]; for(int i = 0;i < n; i++) cin >> a[i]; int prefLongest[n]; vector<int> dp; for(int i = 0; i < n; i++){ int idx = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin(); if(idx == (int)dp.size()){ dp.push_back(a[i]); prefLongest[i] = (int)dp.size(); } else{ dp[idx] = a[i]; prefLongest[i] = idx + 1; } } deque<int> dp2; int ans = 0; for(int i = n - 1; i >= 0; i--){ int idx = upper_bound(dp2.begin(), dp2.end(), a[i] - x) - dp2.begin(); idx--; // cout << (int)dp2.size() - idx - 1 << "\n"; ans = max(ans, (int)dp2.size() - idx - 1 + prefLongest[i]); int idx2 = upper_bound(dp2.begin(), dp2.end(), a[i]) - dp2.begin(); idx2--; if(idx2 == -1){ dp2.push_front(a[i]); } else{ dp2[idx2] = a[i]; } } cout<< ans << "\n"; }
#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...