oj.uz

답안 #207229

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
207229 2020-03-06T19:04:14 Z DodgeBallMan Building Bridges (CEOI17_building) C++14
0 / 100
 74 ms 6264 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;

bool chk[4*N];
int n;
long long sum[M], h[M], dp[M];
pll seg[4*N];

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

void update( pll li, int l = 0, int r = N-1, int idx = 1 ) {
    if( !chk[idx] ) {
        chk[idx] = true, seg[idx] = li;
        return ;
    }
    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 ;
     int mid = l + r >> 1;
    if( get( li, l ) < get( seg[idx], l ) ) swap( seg[idx], li );
    if( l == r ) return ;
    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 = 0, int r = N-1, int idx = 1 ) {
    if( !chk[idx] ) return 1e18;
    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()
{
    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("%d %lld %lld %lld\n",i,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\n",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:25:18: 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:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
building.cpp: In function 'int main()':
building.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
building.cpp:43: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:45: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 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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