Submission #1010185

#TimeUsernameProblemLanguageResultExecution timeMemory
1010185dpsaveslivesGlobal Warming (CEOI18_glo)C++17
10 / 100
41 ms5460 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N,X; cin >> N >> X; vector<int> arr(N); for(int i = 0;i<N;++i){ cin >> arr[i]; } vector<int> dp(N,INT_MAX), L(N,1); int ans = 1; for(int i = 0;i<N;++i){ int ind = lower_bound(dp.begin(),dp.end(),arr[i])-dp.begin(); //first that is >= arr[i] dp[ind] = arr[i]; L[i] = ind+1; ans = max(ans,L[i]); } dp = vector<int>(N+1,INT_MAX); for(int i = N-1;i>=0;--i){ //1 to i have been decreased by X and we want to find the LDS from N-1 to i -> this is equivalent to increasing i by X int ind = lower_bound(dp.begin(),dp.end(),-(arr[i]+X))-dp.begin(); //we want to find the negative version so that we can still lower bound ans = max(ans,L[i]+ind); //no -1 because in ind, i was not counted ind = lower_bound(dp.begin(),dp.end(),-arr[i])-dp.begin(); dp[ind] = -arr[i]; } cout << ans << "\n"; 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...