Submission #619660

#	Time	Username	Problem	Language	Result	Execution time	Memory
619660		chonka	Candies (JOI18_candies)	C++17	100 / 100	115 ms	11956 KiB

candies

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;

const int MAXN = 2e5 + 7 ;
const ll inf = 1e16 ;

int n ;
ll a[ MAXN ] ;

ll sm[ MAXN ] ;
int st[ MAXN ] , en[ MAXN ] ;
bool done[ MAXN ] ;

priority_queue < pair < ll , int > > q ;


void solve ( ) {
    cin >> n ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        cin >> a[ i ] ;
    }
    en[ 0 ] = 1 , st[ n + 1 ] = n ;
    sm[ 0 ] = sm[ n + 1 ] = -inf ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        sm[ i ] = a[ i ] ;
        st[ i ] = i - 1 ;
        en[ i ] = i + 1 ;
        q.push ( { sm[ i ] , i } ) ;
    }

    ll ans = 0 ;
    for ( int i = 1 ; i <= ( n + 1 ) / 2 ; ++ i ) {
        while ( q.empty ( ) == false ) { 
            auto [ aux , wh ] = q.top ( ) ;
            q.pop ( ) ;
            if ( done[ wh ] == true ) { continue ; }
            ans += aux ;
            cout << ans << "\n" ;
            sm[ wh ] = sm[ st[ wh ] ] + sm[ en[ wh ] ] - sm[ wh ] ;
            done[ st[ wh ] ] = done[ en[ wh ] ] = true ;
            q.push ( { sm[ wh ] , wh } ) ;

            st[ wh ] = st[ st[ wh ] ] ;
            en[ st[ wh ] ] = wh ;

            en[ wh ] = en[ en[ wh ] ] ;
            st[ en[ wh ] ] = wh ;
            break ;
        }
    }
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; // cin >> t ; 
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92