# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1085642 | vjudge1 | Global Warming (CEOI18_glo) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,x,a;
cin>>n>>x;
vector<int>v,dp(n,INT_MAX),pref;
for(int i=0;i<n;i++)
{
cin>>a;
v.push_back(a);
}
int res=0;
for(int i=0;i<n;i++)
{
int temp=lower_bound(dp.begin(),dp.end(),v[i])-dp.begin();
pref.push_back(temp+1);
dp[temp]=v[i];
res=max(res,temp+1);
}
for(int i=0;i<n;i++)
{
dp[i]=MAX_INT;
}
for(int i=n-1;i>=0;i--)
{
int temp=lower_bound(dp.begin(),dp.end(),-v[i]+x)-dp.begin();
res=max(res,pref[i]+temp);
temp=lower_bound(dp.begin(),dp.end(),-v[i])-dp.begin();
dp[temp]=-v[i];
}
cout<<res;
return 0;
}