oj.uz

Submission #511521

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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