oj.uz

답안 #207221

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207221 2020-03-06T18:28:42 Z DodgeBallMan Building Bridges (CEOI17_building) C++14
0 / 100
 68 ms 65272 KB 
#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, mid+1, r, idx<<1|1 );
    else swap( seg[idx], li ), update( li, l, mid, idx<<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 <= 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

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:37: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:39: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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Incorrect 36 ms 62968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 68 ms 65272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 62968 KB Output is correct
2 Incorrect 36 ms 62968 KB Output isn't correct
3 Halted 0 ms 0 KB -