Submission #6161

#	Time	Username	Problem	Language	Result	Execution time	Memory
6161		baneling100	Watching (JOI13_watching)	C++98	100 / 100	92 ms	16752 KiB

watching

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

int N, P, Q, A[2001], Max, Min=INF, Ans, Small[2001], Big[2001], D[2001][2001];

void input(void)
{
    int i;

    scanf("%d %d %d",&N,&P,&Q);
    if(P+Q>=N)
    {
        printf("1");
        exit(0);
    }
    for(i=1 ; i<=N ; i++)
    {
        scanf("%d",&A[i]);
        if(Max<A[i])
            Max=A[i];
        if(Min>A[i])
            Min=A[i];
    }
    sort(A+1,A+N+1);
}

int OK(int w)
{
    int i, j, x;

    for(i=1 ; i<=N ; i++)
        if(A[i]-A[1]+1>w)
            break;
    x=i-1;
    Small[1]=x;
    for(i=2 ; i<=N ; i++)
    {
        while(x<N && A[x+1]-A[i]+1<=w)
        {
            x++;
        }
        Small[i]=x;
    }
    for(i=1 ; i<=N ; i++)
        if(A[i]-A[1]+1>2*w)
            break;
    x=i-1;
    Big[1]=x;
    for(i=2 ; i<=N ; i++)
    {
        while(x<N && A[x+1]-A[i]+1<=2*w)
        {
            x++;
        }
        Big[i]=x;
    }
    for(i=0 ; i<=P ; i++)
        for(j=0 ; j<=Q ; j++)
        {
            D[i][j]=0;
            if(i>0)
            {
                if(D[i-1][j]==N)
                    D[i][j]=N;
                else
                    if(D[i][j]<Small[D[i-1][j]+1])
                        D[i][j]=Small[D[i-1][j]+1];
            }
            if(j>0)
            {
                if(D[i][j-1]==N)
                    D[i][j]=N;
                else
                    if(D[i][j]<Big[D[i][j-1]+1])
                        D[i][j]=Big[D[i][j-1]+1];
            }
        }
    if(D[P][Q]==N)
        return 1;
    return 0;
}

void process(void)
{
    int left=1, mid, right=Max-Min+1;

    while(left<=right)
    {
        mid=(left+right)/2;
        if(OK(mid))
        {
            Ans=mid;
            right=mid-1;
        }
        else
            left=mid+1;
    }
}

void output(void)
{
    printf("%d",Ans);
}

int main(void)
{
    input();
    process();
    output();

    return 0;
}

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