Submission #367216

#TimeUsernameProblemLanguageResultExecution timeMemory
367216leu_nautGlobal Warming (CEOI18_glo)C++11
100 / 100
136 ms7028 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll n, x, v[200005], dp[200005]; int main() { cin >> n >> x; for (int i = 0; i < n; i++) cin >> v[i]; vector<ll> lis(n, INT_MAX); ll k = 0; // longest increasing subsequence ending at i for(int i = 0; i < n; i++) { int j = lower_bound(lis.begin(), lis.end(), v[i])-lis.begin(); lis[j] = v[i]; dp[i] = j+1; k = max(k, dp[i]); } lis.assign(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 j = lower_bound(lis.begin(), lis.end(), -v[i]+x)-lis.begin(); int jj = lower_bound(lis.begin(), lis.end(), -v[i])-lis.begin(); lis[jj] = -v[i]; k = max(k, dp[i]+j); } cout << k << 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...