Submission #1086189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086189		serifefedartar	Building Bridges (CEOI17_building)	C++17	0 / 100	56 ms	64600 KiB

building

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 1e6 + 100;

#define int long long
struct Line {
    int m, c;
    int eval(int x) {
        return m * x + c;
    }

    Line() : m(0), c(10000000000000000LL) { }
    Line(int _m, int _c) : m(_m), c(_c) { }
};

vector<int> h, w;
Line sg[4*MAXN];

void add_line(int k, int l, int r, Line new_line) {
    if (l == r) {
        if (new_line.eval(l) < sg[k].eval(l))
            sg[k] = new_line;
        return ;
    }

    int mid = (l + r) / 2;
    if (sg[k].m > new_line.m)
        swap(sg[k], new_line);
    if (sg[k].eval(mid) > new_line.eval(mid)) {
        swap(sg[k], new_line);
        add_line(2*k, l, mid, new_line);
    } else
        add_line(2*k+1, mid+1, r, new_line);
}

int get(int k, int l, int r, int x) {
    if (l == r)
        return sg[k].eval(x);
    if (x <= (l + r) / 2)
        return min(sg[k].eval(x), get(2*k, l, (l+r)/2, x));
    else
        return min(sg[k].eval(x), get(2*k+1, (l+r)/2+1, r, x));
}

signed main() {
    fast;
    int N;
    cin >> N;

    h = vector<int>(N+1, 0);
    w = vector<int>(N+1, 0);
    for (int i = 0; i < 4*MAXN; i++)
        sg[i] = Line();
    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];
    }

    ll ans = 0;
    add_line(1, 1, 1000000, Line(-2 * h[1], h[1] * h[1] - w[1]));
    for (int i = 2; i <= N; i++) {
        ans = h[i] * h[i] + w[i-1] + get(1, 1, 1000000, h[i]);
        add_line(1, 1, 1000000, Line(-2 * h[i], ans + h[i] * h[i] - w[i]));
    }
    cout << ans << "\n";
}

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