Submission #714031

#	Time	Username	Problem	Language	Result	Execution time	Memory
714031		stevancv	Building Bridges (CEOI17_building)	C++14	100 / 100	80 ms	65620 KiB

building

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int M = 1e6 + 2;
const ll linf = 1e18;
ll h[N], w[N];
struct Line {
    ll a, b;
    Line() {
        a = b = linf;
    }
    Line(ll aa, ll bb) {
        a = aa; b = bb;
    }
    ll F(int x) {
        if (a == linf && b == linf) return linf;
        return a * x + b;
    }
} st[4 * M];
void Add(int node, int l, int r, Line lin) {
    int mid = l + r >> 1;
    bool le = lin.F(l) < st[node].F(l);
    bool mi = lin.F(mid) < st[node].F(mid);
    if (mi) swap(lin, st[node]);
    if (l == r) return;
    if (le != mi) Add(2 * node, l, mid, lin);
    else Add(2 * node + 1, mid + 1, r, lin);
}
ll Get(int node, int l, int r, int x) {
    ll ans = st[node].F(x);
    if (l == r) return ans;
    int mid = l + r >> 1;
    if (x <= mid) smin(ans, Get(2 * node, l, mid, x));
    else smin(ans, Get(2 * node + 1, mid + 1, r, x));
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) cin >> w[i], w[i] += w[i - 1];
    for (int i = 1; i <= 4 * n; i++) st[i] = Line();
    Add(1, 0, M, Line(-2 * h[1], h[1] * h[1] - w[1]));
    ll sol = linf;
    for (int i = 2; i < n; i++) {
        ll o = Get(1, 0, M, h[i]) + h[i] * h[i] + w[i - 1];
        Add(1, 0, M, Line(-2 * h[i], o + h[i] * h[i] - w[i]));
    }
    cout << Get(1, 0, M, h[n]) + h[n] * h[n] + w[n - 1] << en;
    return 0;
}

Compilation message (stderr)

building.cpp: In function 'void Add(int, int, int, Line)':
building.cpp:27:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'long long int Get(int, int, int, int)':
building.cpp:38:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = l + r >> 1;
      |               ~~^~~
building.cpp: In function 'int main()':
building.cpp:52:8: warning: unused variable 'sol' [-Wunused-variable]
   52 |     ll sol = linf;
      |        ^~~

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