oj.uz

답안 #511521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
511521 2022-01-16T01:19:20 Z Monarchuwu Building Bridges (CEOI17_building) C++17
100 / 100
 67 ms 37468 KB 
/**
 *  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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33100 KB Output is correct
2 Correct 16 ms 33152 KB Output is correct
3 Correct 14 ms 33048 KB Output is correct
4 Correct 15 ms 33168 KB Output is correct
5 Correct 15 ms 33100 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 62 ms 37256 KB Output is correct
2 Correct 67 ms 37264 KB Output is correct
3 Correct 53 ms 37248 KB Output is correct
4 Correct 50 ms 37136 KB Output is correct
5 Correct 47 ms 37392 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 33100 KB Output is correct
2 Correct 16 ms 33152 KB Output is correct
3 Correct 14 ms 33048 KB Output is correct
4 Correct 15 ms 33168 KB Output is correct
5 Correct 15 ms 33100 KB Output is correct
6 Correct 62 ms 37256 KB Output is correct
7 Correct 67 ms 37264 KB Output is correct
8 Correct 53 ms 37248 KB Output is correct
9 Correct 50 ms 37136 KB Output is correct
10 Correct 47 ms 37392 KB Output is correct
11 Correct 62 ms 37468 KB Output is correct
12 Correct 65 ms 37264 KB Output is correct
13 Correct 53 ms 37380 KB Output is correct
14 Correct 65 ms 37392 KB Output is correct
15 Correct 45 ms 37060 KB Output is correct
16 Correct 45 ms 37116 KB Output is correct
17 Correct 38 ms 37276 KB Output is correct
18 Correct 38 ms 37264 KB Output is correct