Submission #31222

#	Time	Username	Problem	Language	Result	Execution time	Memory
31222		chonka	Watching (JOI13_watching)	C++98	100 / 100	736 ms	17780 KiB

watching

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std ;

#define MAXN 2007
int n , p , q ;
int a[ MAXN ] ;

int dp[ MAXN ][ MAXN ] ;

int small[ MAXN ] ;
int big[ MAXN ] ;

int coef1 , coef2 ;

bool f ( int x ) {
    int i , j ;
    j = 1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        while ( j <= n && ( a[ j ] - a[ i ] + 1 ) <= coef1 * x ) {
            j ++ ;
        }
        j -- ;
        small[ i ] = j ;
    }

    j = 1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        while ( j <= n && ( a[ j ] - a[ i ] + 1 ) <= coef2 * x ) {
            j ++ ;
        }
        j -- ;
        big[ i ] = j ;
    }
    for ( j = 0 ; j <= p ; j ++ ) {
        for ( i = 1 ; i <= n ; i ++ ) {
            dp[ i ][ j ] = q + 27 ;
        }
    }
    for ( j = 0 ; j <= p ; j ++ ) {
        for ( i = j ; i < n ; i ++ ) {
            if ( dp[ i ][ j ] > q ) { continue ; }
            if ( j != p ) {
                dp[ small[ i + 1 ] ][ j + 1 ] = min ( dp[ small[ i + 1 ] ][ j + 1 ] , dp[ i ][ j ] ) ;
            }
            if ( dp[ i ][ j ] != q ) {
                dp[ big[ i + 1 ] ][ j ] = min ( dp[ big[ i + 1 ] ][ j ] , dp[ i ][ j ] + 1 ) ;
            }
        }
        if ( dp[ n ][ j ] <= q ) { return true ; }
    }
    return false ;
}

void input ( ) {
    scanf ( "%d%d%d" , &n , &p , &q ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
    sort ( a + 1 , a + n + 1 ) ;
    if ( p > q ) {
        coef1 = 2 ;
        coef2 = 1 ;
        swap ( p , q ) ;
    }
    else {
        coef1 = 1 ;
        coef2 = 2 ;
    }
}

void solve ( ) {
    if ( ( p + q ) >= n ) { printf ( "1\n" ) ; return ; }
    long long l , r , mid ;
    l = 1 ;
    r = 1 ;
    for ( mid = 1 ; mid <= 9 ; mid ++ ) {
        r *= 10 ;
    }
    r /= 2 ;
    while ( r - l > 3 ) {
        mid = ( l + r ) / 2 ;
        if ( f ( mid ) == true ) { r = mid ; }
        else { l = mid ; }
    }
    while ( f ( l ) == false ) { l ++ ; }
    printf ( "%d\n" , l ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

watching.cpp: In function 'void solve()':
watching.cpp:89:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
     printf ( "%d\n" , l ) ;
                         ^
watching.cpp: In function 'void input()':
watching.cpp:57:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d%d" , &n , &p , &q ) ;
                                       ^
watching.cpp:60:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^

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