제출 #1368649

#제출 시각아이디문제언어결과실행 시간메모리
1368649waygonzBuilding Bridges (CEOI17_building)C++20
100 / 100
51 ms65404 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = (int)1e5 + 1;
const int M = (int)1e6 + 1;
const ll inf = 1e18;

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

struct LiChaoTree {
    struct Line {
        ll m, c;
        ll y(ll x) { return m * x + c; }
        Line() : m(0), c(inf) {}
        Line(ll m, ll c) : m(m), c(c) {}
    };
    Line line[4*M];
    void insert(Line L, int u, int l, int r) {
        int mid = (l + r) / 2;
        bool c1 = line[u].y(l) > L.y(l);
        bool c2 = line[u].y(mid) > L.y(mid);
        if (c2) swap(line[u], L);
        if (l == r) return;
        if (c1 != c2) insert(L, u*2, l, mid);
        else insert(L, u*2+1, mid+1, r);
    }
    ll query(int u, int l, int r, ll x) {
        if (l == r) return line[u].y(x);
        int mid = (l + r) / 2;
        if (x <= mid) return min(line[u].y(x), query(u*2, l, mid, x));
        else return min(line[u].y(x), query(u*2+1, mid+1, r, x));
    }
    void insert(ll m, ll c) { insert(Line(m, c), 1, 1, M); }
    ll query(ll x) { return query(1, 1, M, x); }
} T;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    ll sum = 0;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i], sum += w[i];
    T.insert(-2LL * h[1], h[1] * h[1] - w[1]);
    for (int i = 2; i <= n; i++) {
        dp[i] = T.query(h[i]) + h[i] * h[i] - w[i];
        T.insert(-2LL * h[i], h[i] * h[i] + dp[i]);
    }
    cout << sum + dp[n];
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…