Submission #483422

#TimeUsernameProblemLanguageResultExecution timeMemory
483422keertanGlobal Warming (CEOI18_glo)C++17
100 / 100
46 ms2640 KiB
/** * If you live in imaginary world when your imaginary situation encounter in * real situation you can't enjoiy it because you have to do pending work. * {This pending work appeared because you wasted that time for your useless * imagianry thinking.} */ #include<bits/stdc++.h> using namespace std; //#define int int64_t #define all(x) x.begin(),x.end() #define all1(x) x.rbegin(),x.rend() #define sz(x) (int32_t)(x.size()) const int N=1e2; void solve(){ int n,m; cin>>n>>m; vector<int> z(n); for (int &it:z){cin>>it;} vector<int> dp; int pref[n]; for (int i=0;i<n;i++){ int pos=lower_bound(all(dp),z[i])-dp.begin(); pref[i]=pos+1; if (pos==sz(dp)){ dp.push_back(z[i]); } else{ dp[pos]=z[i]; } } dp.clear(); int ans=0; for (int i=n-1;~i;i--){ int pos=lower_bound(all(dp),-z[i]+m)-dp.begin(); ans=max(ans,pref[i]+pos); pos=lower_bound(all(dp),-z[i])-dp.begin(); if (pos==sz(dp)){ dp.push_back(-z[i]); } else{ dp[pos]=-z[i]; } } cout<<ans; } int32_t main(){ ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); int tq=1; //cin>>tq; for (;tq;tq--){solve();} } //is a bruteforce possible? //think greedier, make more assumptions // if we you find solution using loop to decrease complexity use bs //stuck for more than 5 minutes? move on
#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...