Submission #359103

#	Time	Username	Problem	Language	Result	Execution time	Memory
359103		shahriarkhan	Watching (JOI13_watching)	C++14	100 / 100	99 ms	8684 KiB

watching

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

const int mx = 2005 ;

int a[mx] , dp[mx][mx] , n , p , q ;

set<pair<int,int> > s ;

int check(int w)
{
    for(int i = 0 ; i <= p ; ++i)
    {
        for(int j = 0 ; j <= q ; ++j)
        {
            dp[i][j] = 0 ;
        }
    }
    int comp[n+1][2] ;
    for(int i = 1 ; i <= n ; ++i)
    {
        comp[i][0] = (*(--s.lower_bound({a[i]+w,0}))).second ;
        comp[i][1] = (*(--s.lower_bound({a[i]+w+w,0}))).second ;
    }
    for(int i = 0 ; i <= p ; ++i)
    {
        for(int j = 0 ; j <= q ; ++j)
        {
            if(i)
            {
                dp[i][j] = max(dp[i][j],comp[dp[i-1][j] + 1][0]) ;
            }
            if(j)
            {
                dp[i][j] = max(dp[i][j],comp[dp[i][j-1] + 1][1]) ;
            }
            if(dp[i][j]==n) return 1 ;
        }
    }
    return 0 ;
}

int main()
{
    scanf("%d%d%d",&n,&p,&q) ;
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
    if((p+q)>=n)
    {
        puts("1") ;
        return 0 ;
    }
    sort(a+1,a+n+1) ;
    for(int i = 1 ; i <= n ; ++i) s.insert({a[i],i}) ;
    int low = 0 , high = a[n] ;
    while(low<high)
    {
        int mid = (low+high)/2 ;
        if(check(mid)) high = mid ;
        else low = mid + 1 ;
    }
    printf("%d\n",low) ;
    return 0 ;
}

Compilation message (stderr)

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

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