Submission #31895

#	Time	Username	Problem	Language	Result	Execution time	Memory
31895		chonka	Brunhilda’s Birthday (BOI13_brunhilda)	C++98	41.59 / 100	123 ms	43196 KiB

brunhilda

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

#define MAXN 100007

int n  , m ;
int a[ MAXN ] ;
int b[ MAXN ] ;
int ans[ 100 * MAXN ] ;
int akt[ MAXN ] ;
int lim ;

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

void solve ( ) {
    lim = 1 ;
    int i , j ;
    for ( i = 1 ; i <= 7 ; i ++ ) {
        lim *= 10 ;
    }
    deque < pair < int , int > > q ;
    long long prod = 1 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        prod *= a[ i ] ;
        if ( prod > lim ) { prod = lim + 1 ; }
        q.push_front ( make_pair ( 0 , i ) ) ;
        akt[ i ] = 0 ;
    }
    for ( i = 1 ; i <= lim ; i ++ ) {
        if ( i >= prod ) {
            ans[ i ] = -1 ;
            continue ;
        }
        while ( q.empty ( ) == false ) {
            pair < int , int > p = q.back ( ) ;
            if ( p.first + a[ p.second ] <= i ) {
                q.push_front ( make_pair ( p.first + a[ p.second ] , p.second ) ) ;
                q.pop_back ( ) ;
            }
            else { break ; }
        }
        ans[ i ] = ans[ (q.back()).first ] + 1 ;
        if ( ans[ q.back().first ] == -1 || (q.back()).first == i ) { ans[ i ] = -1 ; }
    }
    while ( m != 0 ) {
        m -- ;
        int x ;
        scanf ( "%d" , &x ) ;
        if ( ans[ x ] != -1 ) {
            printf ( "%d\n" , ans[ x ] ) ;
        }
        else {
            printf ( "oo\n" ) ;
        }
    }

}


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

Compilation message (stderr)

brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:26:13: warning: unused variable 'j' [-Wunused-variable]
     int i , j ;
             ^
brunhilda.cpp: In function 'void input()':
brunhilda.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d%d" , &n , &m ) ;
                                ^
brunhilda.cpp:20:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &a[ i ] ) ;
                                  ^
brunhilda.cpp: In function 'void solve()':
brunhilda.cpp:57:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &x ) ;
                             ^

• Subtask 1: 4.444444444444445 / 20
• Subtask 2: 10 / 20
• Subtask 3: 27.142857142857142 / 60