Submission #373394

#	Time	Username	Problem	Language	Result	Execution time	Memory
373394		Hazem	Watching (JOI13_watching)	C++14	100 / 100	539 ms	16492 KiB

watching

#include <bits/stdc++.h>
using namespace std;
 
#define S second
#define F first
#define LL long long
 
const int N = 2e3+10;

LL LINF = 1e18;
LL INF = 1e9;
LL MOD = 1000000009;

LL a[N];
int nxt[N][2],dp[N][N];
int n,p,q;

int solve(int i,int p1){

    if(i==n+1)
        return 0;
    
    if(dp[i][p1]!=-1)
        return dp[i][p1];
    
    dp[i][p1] = solve(nxt[i][1],p1)+1;
    if(p1)dp[i][p1] = min(dp[i][p1],solve(nxt[i][0],p1-1));
    return dp[i][p1];
}

bool ok(LL mid){

    for(int i=1;i<=n;i++){
        nxt[i][0] = lower_bound(a+1,a+n+1,a[i]+mid)-a;
        nxt[i][1] = lower_bound(a+1,a+n+1,a[i]+mid*2)-a;
    }

    memset(dp,-1,sizeof(dp));
    return solve(1,p)<=q;
}

int main(){

    //freopen("out.txt","w",stdout);
    
    scanf("%d%d%d",&n,&p,&q);
    p = min(p,n);
    q = min(q,n);

    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);

    LL l = 1,r = 1e9;
    while(l<r){
        LL mid = (l+r)/2;
        if(ok(mid))r = mid;
        else l = mid+1;
    }
    printf("%lld\n",l);
}       

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     scanf("%d%d%d",&n,&p,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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