Submission #753932

#	Time	Username	Problem	Language	Result	Execution time	Memory
753932		Johann	Building Bridges (CEOI17_building)	C++14	100 / 100	75 ms	11372 KiB

building

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

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,tune=native")

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const ll INF = 1LL << 60;

int N;
vi H;
vi W;
ll ans;
vi dp;

struct segment
{
    mutable ll l, r;
    ll m, a;
    int type = 0; // 0 - normal, 1 - compare by l, 2 - compare by m
    bool operator<(const segment &o) const
    {
        if (type == 1 || o.type == 1)
            return l < o.l;
        if (type == 2 || o.type == 2)
            return m > o.m;
        return l < o.l;
    }
};
double intersection(ll m1, ll a1, ll m2, ll a2)
{
    return (a1 - a2) / (double)(m2 - m1);
    // todo parallel???
}
struct convexHull
{
    set<segment> H;
    void insert(ll m, ll a)
    {
        auto it1 = H.lower_bound({0, 0, m, 0, 2});
        if (it1 != H.end() && it1->m == m)
        {
            if (it1->a <= a)
                return;
            it1 = H.erase(it1);
        }
        if (it1 == H.begin())
            it1 = H.end();
        else
        {
            --it1; // the elements with o.m > m
            while (intersection(it1->m, it1->a, m, a) < it1->r)
            {
                double inter = intersection(it1->m, it1->a, m, a);
                if (inter < it1->l)
                    it1 = --H.erase(it1);
                else
                    it1->r = (ll)floor(inter);
            }
        }

        auto it2 = H.upper_bound({0, 0, m, 0, 2});
        while (it2 != H.end() && intersection(it2->m, it2->a, m, a) > it2->l)
        {
            double inter = intersection(it2->m, it2->a, m, a);
            if (inter > it2->r)
                it2 = H.erase(it2);
            else
                it2->l = (ll)ceil(inter);
        }

        if (it1 == H.end() || it2 == H.end() || it1->r + 1 < it2->l)
        {
            H.insert({(it1 == H.end()) ? -INF : it1->r + 1, (it2 == H.end()) ? INF : it2->l - 1, m, a, 0});
        }
    }
    ll query(ll x)
    {
        segment seg = *(--H.upper_bound({x, 0, 0, 0, 1}));
        return seg.m * x + seg.a;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    H.resize(N), W.resize(N), dp.resize(N);
    for (int i = 0; i < N; ++i)
        cin >> H[i];
    for (int i = 0; i < N; ++i)
        cin >> W[i];

    ans = accumulate(all(W), 0LL);

    convexHull hull;
    dp[0] = -W[0];

    hull.insert(-2 * H[0], dp[0] + H[0] * H[0]); // first pillar
    for (int i = 1; i < N; ++i)
    {
        dp[i] = hull.query(H[i]) - W[i] + H[i] * H[i];
        hull.insert(-2 * H[i], dp[i] + H[i] * H[i]);
    }

    cout << dp.back() + ans << endl;

    return 0;
}

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