Submission #1358395

#TimeUsernameProblemLanguageResultExecution timeMemory
1358395goulthenBuilding Bridges (CEOI17_building)C++20
100 / 100
32 ms8940 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define pii pair<int,int>
#define fi first
#define se second

const int MAXN = 1e5+10;
const int INF = 1e18+67;
int h[MAXN],w[MAXN], dp[MAXN];


struct Line {
    mutable int k,m,p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(int x) const {return p < x;}
};

struct LineContainer:multiset<Line,less<>> {
    int div(int a, int b) { return a / b - ((a ^ b) < 0 && a % b); }
    bool isect(iterator x, iterator y) {
        if (y == end()) return x->p = INF,0;
        if(x->k == y->k) x->p = x->m>y->m?INF:-INF;
        else x->p = div(y->m-x->m,x->k-y->k);
        return x->p>=y->p;
    }
    void add(int k, int m) {
        auto z = insert({k,m,0}), y = z++, x = y;
        while(isect(y,z)) z = erase(z);
        if(x != begin() && isect(--x,y)) isect(x,y = erase(y));
        while ((y=x)!=begin() && (--x)->p>=y->p) isect(x,erase(y));
    }
    int query(int x) {
        assert(!empty());
        auto it = *lower_bound(x);
        return it.k*x + it.m;
    }
};

int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    int n; cin >> n;
    rep(i,1,n) cin >> h[i];
    rep(i,1,n) cin >> w[i];

    dp[1] = -w[1]+2*h[1]*h[1];
    LineContainer cht;
    cht.add(2*h[1], -dp[1]);
    rep(i,2,n) {
        dp[i] = -cht.query(h[i]) -w[i]+2LL*h[i]*h[i];
        cht.add(2LL*h[i],-dp[i]);
    }
    int sw = 0;
    rep(i,1,n) sw+=w[i];


    cout << dp[n] - h[1]*h[1] - h[n]*h[n] + sw;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...