Submission #540392

#	Time	Username	Problem	Language	Result	Execution time	Memory
540392		krit3379	Watching (JOI13_watching)	C++17	50 / 100	1066 ms	11732 KiB

watching

#include<bits/stdc++.h>
using namespace std;
#define N 2005

long long a[N],dp[N][N],l,r,mid,w,w2,ans;

int main(){
    int n,i,j,p,q;
    scanf("%d %d %d",&n,&p,&q);
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    a[n+1]=1e18;
    sort(a+1,a+n+1);
    if(p+q>=n){printf("1");return 0;}
    l=1,r=1e9;
    while(l<=r){
        mid=(l+r)/2;
        for(i=0;i<=p;i++)for(j=0;j<=q;j++)dp[i][j]=0;
        dp[0][0]=1;
        w=mid-1;
        w2=mid*2-1;
        for(i=1;i<=p;i++)dp[i][0]=upper_bound(a+1,a+n+1,a[dp[i-1][0]]+w)-a;
        for(i=1;i<=q;i++)dp[0][i]=upper_bound(a+1,a+n+1,a[dp[0][i-1]]+w2)-a;
        for(i=1;i<=p;i++){
            for(j=1;j<=q;j++){
                int pos1=upper_bound(a+1,a+n+1,a[dp[i][j-1]]+w2)-a;
                int pos2=upper_bound(a+1,a+n+1,a[dp[i-1][j]]+w)-a;
                dp[i][j]=max(pos1,pos2);
            }
        }
        if(dp[p][q]==n+1)ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

Compilation message (stderr)

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

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