제출 #511521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
511521		Monarchuwu	Building Bridges (CEOI17_building)	C++17	100 / 100	67 ms	37468 KiB

building

/**
 *  Problem:    CEOI17_building
 *  Link:       https://oj.uz/problem/view/CEOI17_building
 *  Tags:       DP, Lichao Tree
 *
 *  Solution:   DP State:       dp[i][j] là xét i cột đầu, end tại j
 *              DP Transition:  dp[i][i] = dp[i - 1][k] + (h[i] - h[k])^2 + (prf[i - 1] - prf[k])
 *                                       = dp[i - 1][k] + h[k]^2 + h[i]^2 - 2 * h[i] * h[k] + prf[i - 1] - prf[k]
 *                                       = (dp[i - 1][k] + h[k]^2 - prf[k]) -2 * h[i] * h[k] + (h[i]^2 + prf[i - 1])
**/
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const ll inf = 1e18;
const int N = 1e5 + 9, H = 1e6;
int n;
ll h[N], w[N], prf[N];

struct Line {
    ll a, b;
    Line(ll a = 0, ll b = inf) : a(a), b(b) {}
    ll operator()(ll x) { return a * x + b; }
} seg[1 << 21];

void upd(int u, int l, int r, Line line) {
    if (l == r) {
        if (seg[u](l) > line(l)) seg[u] = line;
        return;
    }
    int m = (l + r) >> 1;
    if (seg[u].a < line.a) swap(seg[u], line);
    if (seg[u](m) > line(m)) {
        swap(seg[u], line);
        upd(u << 1, l, m, line);
    }
    else upd(u << 1 | 1, m + 1, r, line);
}

ll qry(int u, int l, int r, int x) {
    if (l == r) return seg[u](x);
    int m = (l + r) >> 1;
    if (x <= m)
        return min(seg[u](x), qry(u << 1, l, m, x));
    else return min(seg[u](x), qry(u << 1 | 1, m + 1, r, x));
}

ll dp[N];
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    for (int i = 1; i <= n; ++i) cin >> w[i], prf[i] = prf[i - 1] + w[i];

    upd(1, 0, H, Line(-2 * h[1], h[1] * h[1] - prf[1]));
    for (int i = 2; i < n; ++i) {
        // dp[i][i] = dp[i - 1][k] + (h[i] - h[k])^2 + (prf[i - 1] - prf[k])
        //          = dp[i - 1][k] + h[k]^2 + h[i]^2 - 2 * h[i] * h[k] + prf[i - 1] - prf[k]
        //          = (dp[i - 1][k] + h[k]^2 - prf[k]) -2 * h[i] * h[k] + (h[i]^2 + prf[i - 1])
        dp[i] = qry(1, 0, H, h[i]) + h[i] * h[i] + prf[i - 1];
        upd(1, 0, H, Line(-2 * h[i], dp[i] + h[i] * h[i] - prf[i]));
    }
    cout << qry(1, 0, H, h[n]) + h[n] * h[n] + prf[n - 1] << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/
/*
==================================================+
INPUT:                                            |
--------------------------------------------------|
6
3 8 7 1 6 6
0 -1 9 1 2 0
--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|
17
--------------------------------------------------|
==================================================+
*/

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