답안 #45190

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
45190 2018-04-11T18:29:03 Z chonka Building Bridges (CEOI17_building) C++
100 / 100
181 ms 21088 KB
#include<iostream>
#include<stdio.h>
#include<set>
using namespace std ;

#define MAXN 100007
#define eps 0.00001

long long inf = (long long)1e18 + 7 ;


int n ;
long long a[ MAXN ] ;
long long b[ MAXN ] ;

long long pref[ MAXN ] ;
long long dp[ MAXN ] ;


struct CHT {
    struct line {
        long long coef , add ;
        double nxt_x ;
        int is_query ;
        line ( ) { coef = add = nxt_x = is_query = 0 ; }
        line ( long long _coef , long long _add ) {
            coef = _coef ;
            add = _add ;
            nxt_x = 0 ;
            is_query = 0 ;
        }
        bool operator < ( const line other ) const {
            if ( is_query == 0 && other.is_query == 0 ) { return ( coef > other.coef ) ; }
            return ( nxt_x < other.nxt_x ) ;
        }
        long long value_at ( long long x ) const {
            return ( x * coef + add ) ;
        }
    };
    bool parallel ( line p1 , line p2 ) {
        return ( p1.coef == p2.coef ) ;
    }
    double intersect ( line p1 , line p2 ) {
        if ( parallel ( p1 , p2 ) == true ) { return inf ; }
        ///printf ( "--- %lld %lld with %lld %lld\n" , p1.coef , p1.add , p2.coef , p2.add ) ;
        return ( ( (double)( p2.add - p1.add ) ) / ( p1.coef - p2.coef ) ) ;
    }
    set < line > s ;
    void init ( ) { s.clear ( ) ; }
    bool has_nxt ( set < line > :: iterator it ) {
        if ( it == s.end ( ) ) { return false ; }
        it ++ ;
        if ( it == s.end ( ) ) { return false ; }
        return true ;
    }
    bool has_prv ( set < line > :: iterator it ) {
        if ( it == s.end ( ) ) { return false ; }
        if ( it == s.begin ( ) ) { return false ; }
        return true ;
    }
    set < line > :: iterator get_nxt ( set < line > :: iterator it ) {
        it ++ ; return it ;
    }
    set < line > :: iterator get_prv ( set < line > :: iterator it ) {
        it -- ; return it ;
    }

    bool needless ( line p1 , line p2 , line p3 ) {
        double cross1 = intersect ( p1 , p2 ) ;
        double cross2 = intersect ( p1 , p3 ) ;
        return ( cross2 < cross1 + eps ) ;
    }
    bool needless ( set < line > :: iterator it ) {
        if ( has_prv ( it ) == false ) { return false ; }
        if ( has_nxt ( it ) == false ) { return false ; }
        return needless ( *get_prv ( it ) , *it , *get_nxt ( it ) ) ;
    }
    set < line > :: iterator update ( set < line > :: iterator it ) {
        line aux = (*it) ;
        double ret = inf ;
        if ( has_nxt ( it ) == true ) { ret = intersect ( (*it) , *get_nxt ( it ) ) ; }
        ///printf ( "%.12f\n" , ret ) ;
        it = s.erase ( it ) ;
        aux.nxt_x = ret ;
        it = s.insert ( it , aux ) ;
        ///printf ( "%.12f\n" , it->nxt_x ) ;
        return it ;
    }
    void add_line ( long long _coef , long long _add ) {
        line nw = line ( _coef , _add ) ;
        set < line > :: iterator it = s.lower_bound ( nw ) ;
        if ( it != s.end ( ) && it->coef == nw.coef ) {
            if ( it->add <= nw.add ) { return ; }
            it = s.erase ( it ) ;
        }
        it = s.insert ( it , nw ) ;
        if ( needless ( it ) == true ) {
            s.erase ( it ) ; return ;
        }
        while ( has_prv ( it ) == true && needless ( get_prv ( it ) ) == true ) { s.erase ( get_prv ( it ) ) ; }
        while ( has_nxt ( it ) == true && needless ( get_nxt ( it ) ) == true ) { s.erase ( get_nxt ( it ) ) ; }

        it = update ( it ) ;
        if ( has_prv ( it ) == true ) { update ( get_prv ( it ) ) ; }
        if ( has_nxt ( it ) == true ) { update ( get_nxt ( it ) ) ; }
    }

    long long query ( long long x ) {
        ///printf ( "SET SIZE EQUALS %d\n" , s.size ( ) ) ;
        line aux = line ( ) ;
        aux.nxt_x = x ;
        aux.is_query = 1 ;
        set < line > :: iterator it = s.lower_bound ( aux ) ;
        if ( it == s.end ( ) ) { return inf ; }
        ///printf ( "--- %f\n" , x ) ;
        return it->value_at ( x ) ;
    }
};

CHT w ;

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

void solve ( ) {
    w.init ( ) ;
    int i ;

    w.add_line ( -2 * a[ 1 ] , a[ 1 ] * a[ 1 ] - pref[ 1 ] ) ;
    for ( i = 2 ; i <= n ; i ++ ) {
        long long ret = w.query ( a[ i ] ) ;
        dp[ i ] = ret + a[ i ] * a[ i ] + pref[ i - 1 ] ;
        ///printf ( "%lld, dp[ %d ] = %lld\n" , ret , i , dp[ i ] ) ;
        w.add_line ( -2 * a[ i ] , dp[ i ] + a[ i ] * a[ i ] - pref[ i ] ) ;
    }
    printf ( "%lld\n" , dp[ n ] ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}
/**
6
3 8 7 1 6 6
0 -1 9 1 2 0
**/

Compilation message

building.cpp: In function 'void input()':
building.cpp:123:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
     ~~~~~~^~~~~~~~~~~~~
building.cpp:126:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld" , &a[ i ] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
building.cpp:129:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%lld" , &b[ i ] ) ;
         ~~~~~~^~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 10 ms 408 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 181 ms 3888 KB Output is correct
2 Correct 121 ms 4772 KB Output is correct
3 Correct 110 ms 5840 KB Output is correct
4 Correct 106 ms 6952 KB Output is correct
5 Correct 108 ms 9296 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 10 ms 408 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 181 ms 3888 KB Output is correct
7 Correct 121 ms 4772 KB Output is correct
8 Correct 110 ms 5840 KB Output is correct
9 Correct 106 ms 6952 KB Output is correct
10 Correct 108 ms 9296 KB Output is correct
11 Correct 102 ms 9296 KB Output is correct
12 Correct 132 ms 10040 KB Output is correct
13 Correct 78 ms 11048 KB Output is correct
14 Correct 127 ms 12268 KB Output is correct
15 Correct 119 ms 21088 KB Output is correct
16 Correct 88 ms 21088 KB Output is correct
17 Correct 28 ms 21088 KB Output is correct
18 Correct 33 ms 21088 KB Output is correct