Submission #361194

#	Time	Username	Problem	Language	Result	Execution time	Memory
361194		andreicroitoru	Watching (JOI13_watching)	C++17	100 / 100	280 ms	16128 KiB

watching

#include <bits/stdc++.h>

using namespace std;

const int nax=2001;
int n,p,q;
long long v[2001];
int dp[2001][2001];
bool check(long long w)
{
    if(w<=0)
    {
        return false;
    }
    memset(dp,0,sizeof(dp));
    for(int i=0; i<n; i++)
    {
        int ppp=0;
        while(i-ppp>=0 && v[i]-w+1LL<=v[i-ppp])
        {
            ppp++;
        }
        int pp=0;
        while(i-pp>=0 && v[i]-2LL*w+1<=v[i-pp])
        {
            pp++;
        }
        for(int j=0; j<=q; j++)
        {
            if(i-ppp<0)dp[i][j]=1;
            else dp[i][j]=dp[i-ppp][j]+1;
            if(j!=0)
            {
                if(i-pp<0)
                {
                    dp[i][j]=0;
                }
                else
                {
                    dp[i][j]=min(dp[i][j],dp[i-pp][j-1]);
                }
            }
        }
    }
    return dp[n-1][q]<=p;
}

int main()
{
    cin>>n>>p>>q;
    if(p+q>=n)
    {
        cout<<1<<'\n';
        return 0;
    }
    for(int i=0; i<n; i++)
    {
        cin>>v[i];
    }
    sort(v,v+n);
    long long x=-1,i;
    for(i=1e9; i>=1LL; i/=2LL)
    {
        while(!check(x+i))
        {
            x+=i;
        }
    }
    cout<<x+1<<'\n';
    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50