Submission #1038634

#TimeUsernameProblemLanguageResultExecution timeMemory
1038634DucNguyen2007Global Warming (CEOI18_glo)C++14
100 / 100
42 ms7056 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pll pair<ll,ll> #define fi first #define se second const int maxN=2e5+5; const ll inf=2e18; int n,x,a[maxN+1],dp[maxN+1]; int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>x; for(int i=1;i<=n;i++) { cin>>a[i]; } vector<ll> b(n+1,inf); b[0]=-inf; int mx=0; for(int i=1;i<=n;i++) { int k=lower_bound(b.begin(),b.end(),a[i])-b.begin(); b[k]=a[i]; dp[i]=k; mx=max(mx,k); } vector<ll> c(n+1,inf); c[0]=-inf; for(int i=n;i>=1;i--) { int k=lower_bound(c.begin(),c.end(),x-a[i])-c.begin(); mx=max(mx,dp[i]+k); k=lower_bound(c.begin(),c.end(),-a[i])-c.begin(); c[k]=-a[i]; } cout<<mx-1; }
#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...