Submission #333415

#	Time	Username	Problem	Language	Result	Execution time	Memory
333415		errorgorn	Watching (JOI13_watching)	C++17	100 / 100	933 ms	16312 KiB

watching

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n,c,arr[2005],o,p,k,memo[2005][2005];
int dp(int i,int q){
    int ii=i;
    if (memo[i][q]!=-1) return memo[i][q];
    if (i==n)  return memo[i][q]=0;
    int a;
    a=arr[i]+k-1;
    ii++;
    while (arr[ii]<=a && ii<n){
        ii++;
    }
    if (q==0) return memo[i][q]=(dp(ii,q)+1);
    int b=a+k,j=ii;
    while (arr[j]<=b && j<n){
        j++;
    }
    return memo[i][q]=min((dp(ii,q)+1),dp(j,q-1));
}
void print(){
    for (int x=0;x<=n;x++){
        for (int y=0;y<=n;y++){
            printf("%d ",memo[x][y]);
        }
        printf("\n");
    }
}
int g(int i){
    memset(memo,-1,sizeof(memo));
    k=i;
    return dp(0,o);
}
int main(){
    scanf("%d%d%d",&n,&p,&o);
    int a=0,b=1000000005;
    if (o+p>=n) {printf("1\n");return 0;}
    for (int x=0;x<n;x++){
        scanf("%d",&arr[x]);
    }
    sort(&arr[0],&arr[n]);
    while (true){
        c=(a+b+1)>>1;
        if (c==1) {break;}
        else if (g(c)>p) a=c; // if k==p k-1>p
        else if (g(c-1)<=p) b=c;
        else {printf("%d\n",c);return 0;}
       // printf("%d %d\n",a,b);
    }
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d",&n,&p,&o);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%d",&arr[x]);
      |         ~~~~~^~~~~~~~~~~~~~

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