Submission #77751

#	Time	Username	Problem	Language	Result	Execution time	Memory
77751		nxteru	Watching (JOI13_watching)	C++14	100 / 100	690 ms	16592 KiB

watching

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n,p,q,a[2005],dp[2005][2005];
bool solve(int w){
    if(p+q>=n)return true;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=p;j++){
            dp[i][j]=-1;
        }
    }
    dp[0][p]=q;
    for(int i=0;i<n;i++){
        for(int j=0;j<=p;j++){
            if(dp[i][j]>=0){
                if(dp[i][j]>0){
                    int k=upper_bound(a,a+n,a[i]+w*2-1)-a;
                    dp[k][j]=max(dp[k][j],dp[i][j]-1);
                }
                if(j>0){
                    int k=upper_bound(a,a+n,a[i]+w-1)-a;
                    dp[k][j-1]=max(dp[k][j-1],dp[i][j]);
                }
            }
        }
    }
    for(int i=0;i<=p;i++){
        if(dp[n][i]>=0)return true;
    }
    return false;
}
int main(void){
    scanf("%d%d%d",&n,&p,&q);
    for(int i=0;i<n;i++)scanf("%d",a+i);
    sort(a,a+n);
    int r=0,l=1000000000;
    while(l-r>1){
        int m=(r+l)/2;
        if(solve(m))l=m;
        else r=m;
    }
    printf("%d\n",l);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&p,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:36:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0;i<n;i++)scanf("%d",a+i);
                         ~~~~~^~~~~~~~~~

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