Submission #1075228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075228		ivaziva	Watching (JOI13_watching)	C++14	0 / 100	53 ms	16212 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define MAXN 2001

int n,p,q;
int a[MAXN];
int dp[MAXN][MAXN];

bool check(int w)
{
    for (int i=0;i<MAXN;i++)
    {
        for (int j=0;j<MAXN;j++) dp[i][j]=INT_MAX;
    }
    dp[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        int l1=0,r1=i-1;
        int pos1=i-1;
        while (l1<=r1)
        {
            int mid=(l1+r1)/2;
            if (a[i]-a[mid]>=w) {pos1=mid;l1=mid+1;}
            else r1=mid-1;
        }
        int l2=0,r2=i-1;
        int pos2=i-1;
        while (l2<=r2)
        {
            int mid=(l2+r2)/2;
            if (a[i]-a[mid]>=2*w) {pos2=mid;l2=mid+1;}
            else r2=mid-1;
        }
        for (long long j=0;j<=min(n,q);j++)
        {
            if (dp[pos1][j]==INT_MAX) continue;
            dp[i][j]=min(dp[i][j],dp[pos1][j]+1);
        }
        for (long long j=0;j<min(n,q);j++)
        {
            if (dp[pos2][j]==INT_MAX) continue;
            dp[i][j+1]=min(dp[i][j+1],dp[pos2][j]);
        }
    }
    for (long long i=0;i<=min(n,q);i++)
    {
        if (dp[n][i]<=p) return true;
        else continue;
    }
    return false;
}

int main()
{
    cin>>n>>p>>q;
    for (int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int l=1,r=1000000000;
    int rez=1000000000;
    while (l<=r)
    {
        int mid=(l+r)/2;
        if (check(mid)) {rez=mid;r=mid-1;}
        else l=mid+1;
    }
    cout<<rez<<endl;
}

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