oj.uz

Submission #32217

# Submission time Handle Problem Language Result Execution time Memory
32217 2017-10-04T09:55:10 Z chonka K blocks (IZhO14_blocks) C++
0 / 100
 99 ms 87572 KB 
#include<iostream>
#include<stdio.h>
#include<stack>
using namespace std ;

#define inf 1000000007
#define MAXN 100007
#define MAXK 107

int n , k ;
int a[ MAXN ] ;

long long dp[ MAXN ][ MAXK ] ;

long long vals[ MAXN ] ;
long long pref[ MAXN ] ;

void input ( ) {
    scanf ( "%d%d" , &n , &k ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
    }
}

void solve ( ) {
    stack < int > s ;
    int sz ;
    int i , j ;
    for ( i = 1 ; i <= n ; i ++ ) {
        dp[ i ][ 1 ] = max ( dp[ i - 1 ][ 1 ] , 1LL * a[ i ] ) ;
    }
    pref[ 0 ] = inf ;
    for ( j = 2 ; j <= k ; j ++ ) {
        while ( s.empty ( ) == false ) { s.pop ( ) ; }
        a[ j - 1 ] = inf ;
        s.push ( j - 1 ) ;
        sz = 1 ;
        for ( i = j ; i <= n ; i ++ ) {
            dp[ i ][ j ] = inf ;
            while ( s.empty ( ) == false && a[ s.top ( ) ] <= a[ i ] ) {
                dp[ i ][ j ] = min ( dp[ i ][ j ] , dp[ s.top ( ) ][ j - 1 ] + a[ i ] ) ;
                sz -- ;
                s.pop ( ) ;
            }
            vals[ sz ] = dp[ s.top ( ) ][ j - 1 ] + a[ i ] ;
            pref[ sz ] = min ( pref[ sz - 1 ] , vals[ sz ] ) ;
            dp[ i ][ j ] = min ( dp[ i ][ j ] , pref[ sz ] ) ;
            s.push ( i ) ;
            sz ++ ;
        }
    }
    printf ( "%lld\n" , dp[ n ][ k ] ) ;
}


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

Compilation message

blocks.cpp: In function 'void input()':
blocks.cpp:19:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &k ) ;
                                ^
blocks.cpp:22:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 87572 KB Output is correct
2 Correct 0 ms 87572 KB Output is correct
3 Correct 0 ms 87572 KB Output is correct
4 Correct 0 ms 87572 KB Output is correct
5 Correct 0 ms 87572 KB Output is correct
6 Correct 0 ms 87572 KB Output is correct
7 Correct 0 ms 87572 KB Output is correct
8 Correct 0 ms 87572 KB Output is correct
9 Correct 0 ms 87572 KB Output is correct
10 Correct 0 ms 87572 KB Output is correct
11 Correct 0 ms 87572 KB Output is correct
12 Correct 0 ms 87572 KB Output is correct
13 Incorrect 0 ms 87572 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 87572 KB Output is correct
2 Correct 0 ms 87572 KB Output is correct
3 Correct 0 ms 87572 KB Output is correct
4 Correct 0 ms 87572 KB Output is correct
5 Correct 0 ms 87572 KB Output is correct
6 Correct 0 ms 87572 KB Output is correct
7 Correct 0 ms 87572 KB Output is correct
8 Correct 0 ms 87572 KB Output is correct
9 Correct 0 ms 87572 KB Output is correct
10 Correct 0 ms 87572 KB Output is correct
11 Correct 0 ms 87572 KB Output is correct
12 Incorrect 0 ms 87572 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 87572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 87572 KB Output is correct
2 Correct 13 ms 87572 KB Output is correct
3 Correct 13 ms 87572 KB Output is correct
4 Incorrect 99 ms 87572 KB Output isn't correct
5 Halted 0 ms 0 KB -