oj.uz

Submission #333415

# Submission time Handle Problem Language Result Execution time Memory
333415 2020-12-05T21:55:14 Z errorgorn Watching (JOI13_watching) C++17
100 / 100
 933 ms 16312 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 15980 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 99 ms 15980 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 96 ms 15980 KB Output is correct
8 Correct 100 ms 15980 KB Output is correct
9 Correct 102 ms 15980 KB Output is correct
10 Correct 100 ms 15980 KB Output is correct
11 Correct 111 ms 15980 KB Output is correct
12 Correct 110 ms 15980 KB Output is correct
13 Correct 99 ms 16100 KB Output is correct
14 Correct 105 ms 16108 KB Output is correct
15 Correct 104 ms 15980 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 16108 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 90 ms 16108 KB Output is correct
8 Correct 416 ms 16236 KB Output is correct
9 Correct 189 ms 16236 KB Output is correct
10 Correct 235 ms 16108 KB Output is correct
11 Correct 933 ms 16312 KB Output is correct
12 Correct 782 ms 16236 KB Output is correct
13 Correct 108 ms 16108 KB Output is correct
14 Correct 103 ms 16116 KB Output is correct
15 Correct 101 ms 16236 KB Output is correct