Submission #31908

#	Time	Username	Problem	Language	Result	Execution time	Memory
31908		chonka	K blocks (IZhO14_blocks)	C++98	0 / 100	143 ms	87964 KiB

blocks

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


#define MAXN 100007
#define MAXK 107

int n , k ;
long long a[ MAXN ] ;

long long dp[ MAXN ][ MAXK ] ;


long long val[ MAXN ] ;
long long pref[ MAXN ] ;
long long inf = 0 ;

void input ( ) {
    scanf ( "%d%d" , &n , &k ) ;
    int i ;
    inf = 1 ;
    for ( i = 1 ; i <= 15 ; i ++ ) {
        inf *= 10 ;
    }
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%lld" , &a[ i ] ) ;
    }
    a[ 0 ] = pref[ 0 ] = inf ;
}

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


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

Compilation message (stderr)

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:28:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld" , &a[ i ] ) ;
                                    ^

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