Submission #870815

#	Time	Username	Problem	Language	Result	Execution time	Memory
870815		paduc	Building Bridges (CEOI17_building)	C++17	100 / 100	43 ms	71372 KiB

building

/*
                   /\ \    /\ \
 _____      __     \_\ \   \_\ \  __  __  __  __  __    ___    ____
/\ '__`\  /'__`\   /'_` \  /'_` \/\ \/\ \/\ \/\ \/\ \  /'___\ /',__\
\ \ \L\ \/\ \L\.\_/\ \L\ \/\ \L\ \ \ \_\ \ \ \_/ \_/ \/\ \__//\__, `\
 \ \ ,__/\ \__/.\_\ \___,_\ \___,_\ \____/\ \___x___/'\ \____\/\____/
  \ \ \/  \/__/\/_/\/__,_ /\/__,_ /\/___/  \/__//__/   \/____/\/___/
   \ \_\                 ____________________
    \/_/                /nowl/
*/
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ull unsigned long long
#define ll long long
#define ld double
#define yes {cout << "YES"; return;}
#define no {cout << "NO"; return;}
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using pii = pair<int,int>;
constexpr int mod = 1e9 + 7;
constexpr ll oo = 1e18;
constexpr ld eps = 1e-9;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define fi first
#define se second
#define name "pad"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

template<typename T> bool maximize(T &a, T b) { return a < b && (a = b, true); }
template<typename T> bool minimize(T &a, T b) { return a > b && (a = b, true); }
template<typename T> void compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

struct line{
    int a, b;
    line(int _a = 0, int _b = inf) { a = _a; b = _b; }
    int operator() (int x) { return a * x + b; }
};

struct LiChaoTree{
    vector<line> st; int n, Left, Right;

    LiChaoTree(int _n = 0, int _Left = 0, int _Right = 0) {
        n = _n; Left = _Left; Right = _Right;
        st.resize(n * 4 + 5);
    }

    void update(int id, int l, int r, line d) {

        if(st[id](l) >= d(l) && st[id](r) >= d(r)) {
            st[id] = d;
            return;
        }

        if(st[id](l) <= d(l) && st[id](r) <= d(r)) {
            return;
        }

        int m = (l + r) >> 1;

        if(st[id](l) >= d(l) && st[id](m) >= d(m)) {
            update(id * 2 + 1, m + 1, r, st[id]);
            st[id] = d;
            return;
        }

        if(st[id](l) <= d(l) && st[id](m) <= d(m)) {
            update(id * 2 + 1, m + 1, r, d);
            return;
        }

        if(st[id](m + 1) >= d(m + 1) && st[id](r) >= d(r)) {
            update(id * 2, l, m, st[id]);
            st[id] = d;
            return;
        }

        if(st[id](m + 1) <= d(m + 1) && st[id](r) <= d(r)) {
            update(id * 2, l, m, d);
            return;
        }

    }
    void update(line d) {
        update(1, Left, Right, d);
    }

    int get(int id, int l, int r, int p) {
        int res = st[id](p);
        while(l != r) {
            int m = (l + r) >> 1;
            if(m >= p) id = id * 2, r = m, minimize(res, st[id](p));
            else id = id * 2 + 1, l = m + 1, minimize(res, st[id](p));
        }
        return res;
    }
    int get(int p) {
        return get(1, Left, Right, p);
    }

};

const int N = 1e6 + 5;
int n, h[N], w[N], f[N], sum = 0;

int32_t main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> h[i];
    for(int i = 1; i <= n; ++i) cin >> w[i], sum += w[i];

    LiChaoTree tom(N, 0, 1e6);

    f[1] = -w[1];
    tom.update(line(-2 * h[1], h[1] * h[1] + f[1]));

    for(int i = 2; i <= n; ++i) {
        f[i] = tom.get(h[i]) - w[i] + h[i] * h[i];
        tom.update(line(-2 * h[i], h[i] * h[i] + f[i]));
    }

    cout << f[n] + sum;

    return 0;
}

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