Submission #233801

#	Time	Username	Problem	Language	Result	Execution time	Memory
233801		johutha	Building Bridges (CEOI17_building)	C++14	100 / 100	80 ms	12024 KiB

building

#include <iostream>
#include <vector>
#include <set>

#define int int64_t
#define lint __int128

using namespace std;

struct line
{
    mutable long double leftp = -1e15;
    bool search = false;
    int a, b;

    line() {}
    line(int x) : search(true), a(0), b(x) {}
    line(int ia, int ib) : search(false), a(ia), b(ib) { }

    int get(int x) const
    {
        return a*x + b;
    }

    bool operator<(const line& l2) const
    {
        if (search) return b < l2.leftp;
        if (l2.search) return leftp < l2.b;
        return (a != l2.a) ? a < l2.a : b < l2.b; 
    }

    void recalcleft(set<line>::iterator it) const
    {
        if (a == it->a) return;
        leftp = ((long double)(b - it->b))/ ((long double)(it->a - a));
    }
};

struct hullopt
{
    set<line> hull;

    bool bad(set<line>::iterator it)
    {
        auto nx = next(it);

        if (it == hull.begin())
        {
            if (next(it) == hull.end()) return false;
            return it->a == nx->a && it->b <= nx->b;
        }

        auto pre = prev(it);

        if (nx == hull.end())
        {
            return pre->a == it->a && pre->b >= it->b;
        }

        if (pre->a == it->a && pre->b >= it->b) return true;
        if (nx->a == it->a && nx->b >= it->b) return true;

        return ((lint)(pre->b - it->b))*((lint)(nx->a - pre->a)) >= ((lint)(it->a - pre->a))*((lint)(pre->b - nx->b));
    }

    void insert(int a, int b)
    {
        auto it = hull.insert(line(-a, -b)).first;
        if (bad(it)) { hull.erase(it); return; }

        while (next(it) != hull.end() && bad(next(it))) hull.erase(next(it));
        while (it != hull.begin() && bad(prev(it))) hull.erase(prev(it));
        if (it != hull.begin()) it->recalcleft(prev(it));
        else it->leftp = -1e15;
        if (next(it) != hull.end()) next(it)->recalcleft(it);
    }

    int query(int x)
    {
        auto it = prev(hull.upper_bound(line(x)));
        return -(it->get(x));
    }
};

struct dps
{
    int n;
    vector<int> hs;
    vector<int> cost;
    hullopt hl;
    
    int calculate()
    {
        int res = 0;
        for (auto i : cost) res += i;

        vector<int> dp(n, 0);
        hl.insert(-2*hs[0], hs[0]*hs[0] - cost[0]);

        for (int i = 1; i < n; i++)
        {
            dp[i] = -cost[i] + hs[i]*hs[i];
            dp[i] += hl.query(hs[i]);
            hl.insert(-2*hs[i], hs[i]*hs[i] + dp[i]);
        }
        return res + dp.back();
    }
};

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    dps d;
    d.n = n;
    d.hs.resize(n);
    d.cost.resize(n);

    for (int i = 0; i < n; i++) cin >> d.hs[i];
    for (int i = 0; i < n; i++) cin >> d.cost[i];

    cout << d.calculate() << "\n";
}

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