Submission #1185835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185835		belgianbot	Building Bridges (CEOI17_building)	C++20	100 / 100	40 ms	15312 KiB

building

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct f {
    int m, p;
    int calc(int x){return m * x + p;}
};

vector<int> cost, h, dp;
vector<f> li_chao;
int N;
const int maxN = 2e5;


void add_line(f nw, int i = 1, int l = 0, int r = maxN) {
    int mid = (l+r) / 2;
    bool better = nw.calc(l) < li_chao[i].calc(l);
    bool betterMid = nw.calc(mid) < li_chao[i].calc(mid);

    if (betterMid) swap(nw, li_chao[i]);
    
    if (l == r) return;
    else if (better != betterMid) add_line(nw, i * 2, l, mid);
    else add_line(nw, i * 2 + 1, mid+1, r);
}

int query (int x, int i = 1, int l = 0, int r = maxN) {
    int mid = (l+r)/2;
    if (l == r) return li_chao[i].calc(x);
    else if (x <= mid) return min(li_chao[i].calc(x), query(x, i * 2, l, mid));
    else return min(li_chao[i].calc(x), query(x, i*2+1, mid+1, r));
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    
    //f a = {0, (int)(1e9)};
    li_chao.resize(4*maxN, {0, (int)(1e32)}); h.resize(N); cost.resize(N);
    for (int i = 0; i < N; i++) cin >> h[i];
    for (int i = 0; i < N; i++) cin >> cost[i];

    dp.resize(N); dp[N-1] = 0;
    int sum = cost[N-1];
    add_line({-2*h[N-1], h[N-1] *h[N-1] - sum});
    for (int i = N - 2; i >= 0; i--) {
        int best = query(h[i]);
        dp[i] = best + h[i] * h[i] + sum;
        sum += cost[i];
        add_line({-2*h[i], h[i] * h[i] + dp[i] - sum});
        
    }

    cout << dp[0] << '\n';
    return 0;
}

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