Submission #38671

#	Time	Username	Problem	Language	Result	Execution time	Memory
38671		chonka	Luxury burrow (IZhO13_burrow)	C++98	100 / 100	843 ms	5992 KiB

burrow

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

#define MAXN 1007

int n , m , k ;
int a[ MAXN ][ MAXN ] ;
int h[ MAXN ] ;

int st[ MAXN ] ;
int en[ MAXN ] ;
int ans ;

bool f ( int x ) {
    int i , j ;
    int mx = 0 ;
    for ( i = 1 ; i <= m ; i ++ ) { h[ i ] = 0 ; }
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 1 ; j <= m ; j ++ ) {
            if ( a[ i ][ j ] >= x ) {
                h[ j ] ++ ;
            }
            else { h[ j ] = 0 ; }
        }
        stack < int > s ;
        while ( s.empty ( ) == false ) { s.pop ( ) ; }
        h[ 0 ] = h[ m + 1 ] = -1 ;
        s.push ( 0 ) ;
        for ( j = 1 ; j <= m ; j ++ ) {
            while ( h[ s.top ( ) ] >= h[ j ] ) { s.pop ( ) ; }
            st[ j ] = s.top ( ) ;
            s.push ( j ) ;
        }
        while ( s.empty ( ) == false ) { s.pop ( ) ; }
        s.push ( m + 1 ) ;
        for ( j = m ; j >= 1 ; j -- ) {
            while ( h[ s.top ( ) ] >= h[ j ] ) { s.pop ( ) ; }
            en[ j ] = s.top ( ) ;
            s.push ( j ) ;
        }
        for ( j = 1 ; j <= m ; j ++ ) {
            int cur = h[ j ] * ( en[ j ] - st[ j ] - 1 ) ;
            if ( mx < cur ) { mx = cur ; }
        }
    }
    ans = mx ;
    return ( mx >= k ) ;
}

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

void solve ( ) {
    int 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 ) { l = mid ; }
        else { r = mid ; }
    }
    while ( f ( r ) == false ) { r -- ; }
    printf ( "%d %d\n" , r , ans ) ;
}

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

Compilation message (stderr)

burrow.cpp: In function 'void input()':
burrow.cpp:53:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d%d" , &n , &m , &k ) ;
                                       ^
burrow.cpp:57:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf ( "%d" , &a[ i ][ j ] ) ;
                                           ^

• Subtask 1: 100 / 100