oj.uz

Submission #438789

# Submission time Handle Problem Language Result Execution time Memory
438789 2021-06-28T15:25:42 Z MilosMilutinovic Watching (JOI13_watching) C++14
100 / 100
 286 ms 16840 KB 
#include <bits/stdc++.h>
using namespace std;

const int N=2050;

int n,p,q,a[N],dp[N][N];
bool Check(int w){
    memset(dp,1e9,sizeof dp);
    dp[0][0]=0;
    int x=0,y=0;
    for(int i=1;i<=n;i++){
        while(a[i]-a[x+1]>=w)x++;
        while(a[i]-a[y+1]>=2*w)y++;
        for(int j=0;j<=n;j++){
            dp[i][j]=dp[x][j]+1;
            if(j>0)dp[i][j]=min(dp[i][j],dp[y][j-1]);
        }
    }
    for(int j=0;j<=min(n,q);j++){
        if(dp[n][j]<=p)return true;
    }
    return false;
}

int main(){
    scanf("%i %i %i",&n,&p,&q);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    sort(a+1,a+n+1);
    int bot=1,top=1e9,ans=1e9;
    while(bot<=top){
        int mid=bot+top>>1;
        if(Check(mid))ans=mid,top=mid-1;
        else bot=mid+1;
    }
    printf("%i",ans);
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:31:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         int mid=bot+top>>1;
      |                 ~~~^~~~
watching.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     scanf("%i %i %i",&n,&p,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:27:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for(int i=1;i<=n;i++)scanf("%i",&a[i]);
      |                          ~~~~~^~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16716 KB Output is correct
2 Correct 77 ms 16840 KB Output is correct
3 Correct 73 ms 16716 KB Output is correct
4 Correct 72 ms 16716 KB Output is correct
5 Correct 71 ms 16724 KB Output is correct
6 Correct 70 ms 16720 KB Output is correct
7 Correct 79 ms 16716 KB Output is correct
8 Correct 68 ms 16716 KB Output is correct
9 Correct 71 ms 16720 KB Output is correct
10 Correct 68 ms 16724 KB Output is correct
11 Correct 71 ms 16724 KB Output is correct
12 Correct 75 ms 16716 KB Output is correct
13 Correct 81 ms 16724 KB Output is correct
14 Correct 71 ms 16732 KB Output is correct
15 Correct 72 ms 16644 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 16740 KB Output is correct
2 Correct 79 ms 16716 KB Output is correct
3 Correct 239 ms 16756 KB Output is correct
4 Correct 230 ms 16740 KB Output is correct
5 Correct 227 ms 16740 KB Output is correct
6 Correct 233 ms 16740 KB Output is correct
7 Correct 286 ms 16716 KB Output is correct
8 Correct 240 ms 16740 KB Output is correct
9 Correct 254 ms 16700 KB Output is correct
10 Correct 241 ms 16744 KB Output is correct
11 Correct 248 ms 16744 KB Output is correct
12 Correct 240 ms 16744 KB Output is correct
13 Correct 238 ms 16740 KB Output is correct
14 Correct 237 ms 16744 KB Output is correct
15 Correct 237 ms 16820 KB Output is correct