제출 #961842

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961842		LucaIlie	Building Bridges (CEOI17_building)	C++17	100 / 100	81 ms	66492 KiB

building

#include <bits/stdc++.h>

using namespace std;

struct func1 {
    long long a, b;

    long long operator() ( long long x ) {
        return a * x + b;
    }
};

const int MAX_N = 1e5;
const int MAX_H = 1e6;
long long h[MAX_N], w[MAX_N], dp[MAX_N];
func1 maxFunc[4 * MAX_H];

void addLine( int v, int l, int r, func1 f ) {
    int mid = (l + r) / 2;

    if ( maxFunc[v].a < f.a )
        swap( maxFunc[v], f );

    if ( f( mid ) < maxFunc[v]( mid ) ) {
        swap( maxFunc[v], f );
        if ( l != r )
            addLine( v * 2 + 1, l, mid, f );
    } else {
        if ( l != r )
            addLine( v * 2 + 2, mid + 1, r, f );
    }
}

long long getMin( int v, int l, int r, int x ) {
    if ( l == r )
        return maxFunc[v]( x );

    int mid = (l + r) / 2;
    if ( x <= mid )
        return min( maxFunc[v]( x ), getMin( v * 2 + 1, l, mid, x ) );
    return min( maxFunc[v]( x ), getMin( v * 2 + 2, mid + 1, r, x ) );
}

int main() {
    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ )
        cin >> h[i];
    for ( int i = 0; i < n; i++ )
        cin >> w[i];
    for ( int i = 1; i < n; i++ )
        w[i] += w[i - 1];

    for ( int v = 0; v < 4 * MAX_H; v++ )
        maxFunc[v] = { (long long)1e7, (long long)1e12 };
    addLine( 0, 1, MAX_H, { -2 * h[0], dp[0] - w[0] + h[0] * h[0] } );
    for ( int i = 1; i < n; i++ ) {
        dp[i] = getMin( 0, 1, MAX_H, h[i] ) + w[i - 1] + h[i] * h[i];
        addLine( 0, 1, MAX_H, { -2 * h[i], dp[i] - w[i] + h[i] * h[i] } );
    }

    cout << dp[n - 1];

    return 0;
}

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