Submission #359099

#	Time	Username	Problem	Language	Result	Execution time	Memory
359099		shahriarkhan	Watching (JOI13_watching)	C++14	50 / 100	1083 ms	8812 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 ;
        }
    }
    for(int i = 0 ; i <= p ; ++i)
    {
        for(int j = 0 ; j <= q ; ++j)
        {
            if(i)
            {
                pair<int,int> cur = *(--s.lower_bound({a[dp[i-1][j]+1]+w,0})) ;
                dp[i][j] = max(dp[i][j],cur.second) ;
            }
            if(j)
            {
                pair<int,int> cur = *(--s.lower_bound({a[dp[i][j-1]+1]+w+w,0})) ;
                dp[i][j] = max(dp[i][j],cur.second) ;
            }
            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:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |     scanf("%d%d%d",&n,&p,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
watching.cpp:42:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
      |                                   ~~~~~^~~~~~~~~~~~

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