제출 #133217

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133217		lyc	Building Bridges (CEOI17_building)	C++14	100 / 100	144 ms	12536 KiB

building

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;

int N;
int H[MAXN];
ll W[MAXN];

const ll is_query = -(1LL<62);

struct Line {
    ll m, b;
    mutable function<const Line*()> succ;
    bool operator<(const Line& rhs) const {
        if (rhs.b != is_query) return m > rhs.m;
        const Line* s = succ();
        if (!s) return 0;
        ll x = rhs.m;
        return b - s->b >= (s->m - m) * x;
    }
};

struct HullDynamic : public multiset<Line> {
    bool bad(iterator y) {
        auto z = next(y);
        if (y == begin()) {
            if (z == end()) return 0;
            return y->m == z->m and y->b > z->b;
        }
        auto x = prev(y);
        if (z == end()) return y->m == x->m and y->b > x->b;
        return (y->b - z->b) * (y->m - x->m) <= (x->b - y->b) * (z->m - y->m);
    }

    void add(Line l) {
        auto y = insert(l);
        y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
        if (bad(y)) { erase(y); return; }
        while (y != begin() and bad(prev(y))) erase(prev(y));
        while (next(y) != end() and bad(next(y))) erase(next(y));
    }

    ll query(ll x) {
        auto l = *lower_bound({ x, is_query });
        return l.m * x + l.b;
    }
} ch;

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N){ cin >> H[i]; }
    W[0] = 0;
    FOR(i,1,N){ cin >> W[i]; W[i] += W[i-1]; }

    //res[i] = res[j] + W[j-1]-W[i] + H[i]*H[i] - 2*H[i]*H[j] + H[j]*H[j];
    //res[i] = -W[i]+H[i]*H[i] -2*H[i]*H[j] + H[j]*H[j] + res[j] + W[j-1];
    ll res[N+1];
    res[N] = 0; ch.add({-2LL*H[N], (ll)H[N]*H[N] + res[N] + W[N-1]});
    RFOR(i,N-1,1){
        res[i] = (ll)-W[i]+(ll)H[i]*H[i] + ch.query(H[i]);
        ch.add({-2LL*H[i], (ll)H[i]*H[i] + res[i] + W[i-1]});
    }

    cout << res[1] << '\n';
}

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