Submission #515722

#	Time	Username	Problem	Language	Result	Execution time	Memory
515722		andrei_boaca	Global Warming (CEOI18_glo)	C++17	28 / 100	2080 ms	4872 KiB

glo

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,x,v[200005],ans,dp[200005],maxim[200005];
ll getLIS()
{
    ll rez=0;
    for(int i=1;i<=n;i++)
        maxim[i]=-2e9;
    for(int i=n;i>=1;i--)
    {
        int lg=0;
        int st=1;
        int dr=n-i;
        while(st<=dr)
        {
            int mij=(st+dr)/2;
            if(maxim[mij]>v[i])
            {
                lg=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        dp[i]=lg+1;
        rez=max(rez,dp[i]);
        maxim[dp[i]]=max(maxim[dp[i]],v[i]);
    }
    return rez;
}
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    ans=getLIS();
    for(int i=1;i<=n;i++)
    {
        v[i]-=x;
        ans=max(ans,getLIS());
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25