oj.uz

Submission #31222

# Submission time Handle Problem Language Result Execution time Memory
31222 2017-08-14T09:26:04 Z chonka Watching (JOI13_watching) C++
100 / 100
 736 ms 17780 KB 
#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

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.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17780 KB Output is correct
2 Correct 0 ms 17780 KB Output is correct
3 Correct 0 ms 17780 KB Output is correct
4 Correct 0 ms 17780 KB Output is correct
5 Correct 0 ms 17780 KB Output is correct
6 Correct 0 ms 17780 KB Output is correct
7 Correct 0 ms 17780 KB Output is correct
8 Correct 0 ms 17780 KB Output is correct
9 Correct 0 ms 17780 KB Output is correct
10 Correct 0 ms 17780 KB Output is correct
11 Correct 0 ms 17780 KB Output is correct
12 Correct 0 ms 17780 KB Output is correct
13 Correct 0 ms 17780 KB Output is correct
14 Correct 0 ms 17780 KB Output is correct
15 Correct 0 ms 17780 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17780 KB Output is correct
2 Correct 0 ms 17780 KB Output is correct
3 Correct 0 ms 17780 KB Output is correct
4 Correct 0 ms 17780 KB Output is correct
5 Correct 0 ms 17780 KB Output is correct
6 Correct 0 ms 17780 KB Output is correct
7 Correct 9 ms 17780 KB Output is correct
8 Correct 69 ms 17780 KB Output is correct
9 Correct 69 ms 17780 KB Output is correct
10 Correct 33 ms 17780 KB Output is correct
11 Correct 43 ms 17780 KB Output is correct
12 Correct 736 ms 17780 KB Output is correct
13 Correct 13 ms 17780 KB Output is correct
14 Correct 13 ms 17780 KB Output is correct
15 Correct 13 ms 17780 KB Output is correct