Submission #1296920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296920		datluong_04	Building Bridges (CEOI17_building)	C++20	0 / 100	33 ms	3776 KiB

building

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define FOR(i , a , b) for(int i = a ; i <= b; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define maxn 100005

struct line{
    ll m , c;
    line(ll a , ll b){m = a , c = b;}
};

struct Convex_Hull_Trick{
    vector<line> v;
    void init(int tp){v.clear();}
    bool bad(line l1 , line l2 , line l3){
        ll a = (l2.c - l1.c) * (l2.m - l3.m);
        ll b = (l3.c - l2.c) * (l1.m - l2.m);
        return a <=  b;
    }

    void add(line a){
        if(!v.empty() && v.back().m == a.m){
            if(v.back().c >= a.c) return;
            v.pop_back();
        }

        while(v.size() >= 2 && bad(v[v.size() - 2] , v[v.size() - 1] , a)){
            v.pop_back();
        }
        v.push_back(a);
    }

    ll val(int j , ll x){
        return v[j].m * x +  v[j].c;
    }

    ll query(ll x){
        int l = 0;
        int r = v.size() - 1;
        // max
        ll ans = 0;
        while(l <= r){
            int mid1 = l + (r - l) / 3;
            int mid2 = r - (r - l) / 3;
            if(val(mid1 , x) <= val(mid2 , x)){
                ans = val(mid1 , x);
                r = mid2 - 1;
            }
            else{
                ans = val(mid2 , x);
                l = mid1 + 1;
            }
        }
        return ans;
    }

};

ll dp[maxn] , w[maxn] , h[maxn];

int main(){
    FAST;
    int n;
    cin >> n;
    FOR(i , 1 , n) cin >> h[i];
    ll sum_w = 0;
    FOR(i , 1 , n){
        cin >> w[i];
        sum_w += w[i];
    }

    Convex_Hull_Trick C;
    // goi dp(i) la min cost khi xet den cot i 
    // dp(i) = min(dp(j) + (hi - hj)^2 - wi)
    // dp(i) = -wi + hi*hi + min(dp(j) + hj^2 - 2hihj )
    // dp(i) = -wi + hi^2 + min(c + mx) voi hi = x
    dp[1] = -w[1];
    C.add({-2 * h[1] , dp[1] + h[1] * h[1]});
    FOR(i , 2 , n){
        ll y = C.query(h[i]);
        dp[i] = y - w[i] + h[i] * h[i];
        C.add({-2 * h[i] , dp[i] + h[i] * h[i]});
    }
    cout << sum_w + dp[n];
}

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