Submission #1241766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241766		Bahamin	Building Bridges (CEOI17_building)	C++20	100 / 100	38 ms	7748 KiB

building

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const ld EPS = 1e-9;
const int LOG = 30;

inline ll divf(ll a, ll b) {
    assert(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(y!=end() && x->m==y->m) {
            if(x->c<=y->c) {
                erase(x);
                return;
            }
            y = erase(y);
        }
        if(x!=begin() && prev(x)->m==x->m) {
            if(x->c<=prev(x)->c) {
                erase(x);
                return;
            }
            erase(prev(x));
        }
        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;
    }
};

cht lines;

void solve() {
    int n;
    cin >> n;
    int h[n];
    for (int i = 0; i < n; i++) cin >> h[i];
    int w[n];
    for (int i = 0; i < n; i++) cin >> w[i];
    ll dp[n];
    dp[0] = 0;
    lines.add(2 * h[0], w[0] - 1ll * h[0] * h[0]);
    ll sum = w[0];
    for (int i = 1; i < n; i++)
    {
        dp[i] = sum + 1ll * h[i] * h[i] - lines.get(h[i]);
        sum += w[i];
        lines.add(2 * h[i], -dp[i] + sum - 1ll * h[i] * h[i]);
    }
    cout << dp[n - 1] << "\n";
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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