Submission #207219

#	Time	Username	Problem	Language	Result	Execution time	Memory
207219		DodgeBallMan	Building Bridges (CEOI17_building)	C++14	0 / 100	81 ms	65272 KiB

building

#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define x first
#define y second

using namespace std;

const int N = 1e6 + 10;
const int M = 1e5 + 10;
int n;
long long sum[M], h[M], dp[M];
pll seg[4*N], zero;

long long get( pll a, long long x ) { return a.x * x + a.y; }

void update( pll li, int l = 1, int r = N - 9, int idx = 1 ) {
    if( get( li, l ) <= get( seg[idx], l ) && get( li, r ) <= get( seg[idx], r ) ) return void( seg[idx] = li );
    else if( get( li, l ) >= get( seg[idx], l ) && get( li, r ) >= get( seg[idx], r ) ) return ;
    if( get( li, l ) >= get( seg[idx], l ) ) swap( seg[idx], li );
    if( l == r ) return ;
    int mid = l + r >> 1;
    if( get( li, mid ) >= get( seg[idx], mid ) ) update( li, l, mid, idx<<1 );
    else swap( seg[idx], li ), update( li, mid + 1, r, idx<<1|1 );
}

long long query( long long x, int l = 1, int r = N - 9, int idx = 1 ) {
    if( l == r ) return get( seg[idx], x );
    int mid = l + r >> 1;
    if( idx <= mid ) return min( query( x, l, mid, idx<<1 ), get( seg[idx], x ) );
    else return min( get( seg[idx], x ), query( x, mid + 1, r, idx<<1|1 ) );
}

int main()
{
    fill_n( seg, 4*N, pll( 1e12, 1e12 ) );
    scanf("%d",&n);
    for( int i = 1 ; i < 4*N ; i++ ) seg[i] = zero;
    for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&h[i]);
    for( int i = 1 ; i <= n ; i++ ) {
        scanf("%lld",&sum[i]);
        sum[i] += sum[i-1];
    }
    for( int i = 1 ; i <= n ; i++ ) {
        if( i > 1 ) dp[i] = query( h[i] ) + h[i] * h[i] + sum[i-1];
        //printf("%lld %lld %lld\n",query( h[i] ), sum[i-1],dp[i]);
        update( pll( -2LL*h[i], h[i]*h[i] - sum[i] + dp[i] ) );
        
    }
    //printf("\n");
    printf("%lld",dp[n]);
    return 0;
}

Compilation message (stderr)

building.cpp: In function 'void update(std::pair<long long int, long long int>, int, int, int)':
building.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
building.cpp: In function 'long long int query(long long int, int, int, int)':
building.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
building.cpp: In function 'int main()':
building.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
building.cpp:38:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for( int i = 1 ; i <= n ; i++ ) scanf("%lld",&h[i]);
                                     ~~~~~^~~~~~~~~~~~~~
building.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&sum[i]);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40