oj.uz

Submission #31219

# Submission time Handle Problem Language Result Execution time Memory
31219 2017-08-14T09:21:23 Z chonka Watching (JOI13_watching) C++
50 / 100
 1000 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 ] ;

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

    j = 1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        while ( j <= n && ( a[ j ] - a[ i ] + 1 ) <= 2 * 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 = 0 ; 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 ) ;
            }
        }
    }
    for ( j = 0 ; j <= p ; j ++ ) {
        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 ) ;
}

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 ;
    }
    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:79: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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 16 ms 17780 KB Output is correct
8 Correct 96 ms 17780 KB Output is correct
9 Execution timed out 1000 ms 17780 KB Execution timed out
10 Halted 0 ms 0 KB -