Submission #32018

#	Time	Username	Problem	Language	Result	Execution time	Memory
32018		chonka	Hacker (BOI15_hac)	C++98	100 / 100	99 ms	32368 KiB

hac

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

#define MAXN 500007

int n ;
int a[ 3 * MAXN ] ;
long long pref[ 3 * MAXN ] ;

long long val[ 3 * MAXN ] ;

int len ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    len = ( n / 2 ) + ( n % 2 ) ;
    int i ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        a[ n + i ] = a[ i ] ;
        a[ 2 * n + i ] = a[ i ] ;
    }
    for ( i = 1 ; i <= 3 * n ; i ++ ) {
        pref[ i ] = ( pref[ i - 1 ] + a[ i ] ) ;
    }
    for ( i = 1 ; i + len - 1 <= 3 * n ; i ++ ) {
        val[ i ] = pref[ i + len - 1 ] - pref[ i - 1 ] ;
    }
}

void solve ( ) {
    int i ;
    deque < int > q ;
    long long ans = 0 ;
    for ( i = 1 ; i <= 3 * n ; i ++ ) {
        while ( q.empty ( ) == false && val[ q.back ( ) ] >= val[ i ] ) {
            q.pop_back ( ) ;
        }
        q.push_back ( i ) ;
        while ( q.empty ( ) == false && q.front ( ) + len - 1 < i ) {
            q.pop_front ( ) ;
        }
        if ( i > n && i <= 2 * n ) {
            ans = max ( ans , val[ q.front ( ) ] ) ;
        }
    }
    printf ( "%lld\n" , ans ) ;
}

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

Compilation message (stderr)

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

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 40 / 40