Submission #374051

#	Time	Username	Problem	Language	Result	Execution time	Memory
374051		denkendoemeer	Watching (JOI13_watching)	C++14	100 / 100	182 ms	16108 KiB

watching

#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
using namespace std;
int v[2005],dp[2005][2005];
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,x,y,i;
    scanf("%d%d%d",&n,&x,&y);
    if (n<y)
        y=n;
    if (n-y<x)
        x=n-y;
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    sort(v+1,v+n+1);
    int st=1,dr=v[n]-v[1]+1,mij;
    while(st<dr){
        mij=(st+dr)/2;
        int a=0,b=0;
        for(i=0;i<=n;i++){
            while(a<=i && v[a]<=v[i]-mij)
                a++;
            while(b<=i && v[b]<=v[i]-2*mij)
                b++;
            int j;
            for(j=!i;j<=x;j++){
                dp[i][j]=i?j?min(dp[a-1][j-1],dp[b-1][j]+1):dp[b-1][j]+1:0;
            }
        }
        if (dp[n][x]<=y)
            dr=mij;
        else
            st=mij+1;
    }
    printf("%d\n",dr);
return 0;
}

Compilation message (stderr)

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

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