Submission #1227015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227015		Hamed_Ghaffari	Building Bridges (CEOI17_building)	C++20	0 / 100	10 ms	1604 KiB

building

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

using ll = long long;

const ll inf = 1e18;

inline ll divf(ll a, ll b) {
    return a/b - ((a^b)<0 && a%b);
}

struct line {
    mutable ll m, c, p;
    bool operator<(const line &l) const { return m < l.m; }
    bool operator<(ll x) const { return p < x; }
};

struct cht : multiset<line, less<>> {
private:
    inline ll isect(iterator x, iterator y) {
        return divf(x->c-y->c, y->m-x->m);
    }
public:
    inline void add(ll m, ll c) {
        auto y = insert({m, c, inf}), x = y++;
        if(empty()) return;
        if(x!=begin() && y!=end() && isect(x, y)<=prev(x)->p) {
            erase(x);
            return;
        }
        while(y!=end()) {
            ll p = isect(x, y);
            if(p>=y->p) y = erase(y);
            else {
                x->p = p;
                break;
            }
        }
        if(x==begin()) return;
        y = x--;
        while(x!=begin() && isect(prev(x), y)<=prev(x)->p) {
            erase(x);
            x = prev(y);
        }
        x->p = isect(x, y);
    }
    inline ll get(ll x) {
        assert(!empty());
        auto it = lower_bound(x);
        return it->m*x + it->c;
    }
};

const int MXN = 1e5+5;

int n, h[MXN];
ll w[MXN], dp[MXN];
cht ds;

inline void add(int j) {
    ds.add(2*h[j], -(dp[j]+1ll*h[j]*h[j]-w[j]));
}

inline ll get(int i) {
    return -ds.get(h[i]) + 1ll*h[i]*h[i] + w[i-1];
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    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];
    add(1);
    for(int i=2; i<=n; i++) {
        dp[i] = get(i);
        add(i);
    }
    cout << dp[n] << '\n';
    return 0;
}

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