Submission #32219

#	Time	Username	Problem	Language	Result	Execution time	Memory
32219		chonka	K blocks (IZhO14_blocks)	C++98	100 / 100	693 ms	87832 KiB

blocks

#include<iostream>
#include<stdio.h>
#include<stack>
#include<cstring>
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 < pair < int , int > > s ;
    int sz ;
    int i , j ;
    for ( i = 0 ; i <= n ; i ++ ) {
        for ( j = 0 ; j <= k ; j ++ ) {
            dp[ i ][ j ] = inf ;
        }
    }
    dp[ 0 ][ 0 ] = 0 ;
    for ( j = 1 ; j <= k ; j ++ ) {
        while ( s.empty ( ) == false ) { s.pop ( ) ; }
        s.push ( make_pair ( inf , inf ) ) ;
        for ( i = 1 ; i <= n ; i ++ ) {
            long long aux = dp[ i - 1 ][ j - 1 ] ;
            while ( s.empty ( ) == false && s.top( ).first <= a[ i ] ) {
                aux = min ( aux , 1LL * s.top().second ) ;
                s.pop ( ) ;
            }
            dp[ i ][ j ] = min ( 1LL * s.top( ).first + s.top ( ).second , aux + a[ i ] ) ;
            if ( aux + a[ i ] < s.top ( ).first + s.top ( ).second ) {
                s.push ( make_pair ( a[ i ] , aux ) ) ;
            }
        }
    }
    printf ( "%lld\n" , dp[ n ][ k ] ) ;
}


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

Compilation message (stderr)

blocks.cpp: In function 'void solve()':
blocks.cpp:30:9: warning: unused variable 'sz' [-Wunused-variable]
     int sz ;
         ^
blocks.cpp: In function 'void input()':
blocks.cpp:21: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:24:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47