oj.uz

Submission #233801

# Submission time Handle Problem Language Result Execution time Memory
233801 2020-05-21T18:22:37 Z johutha Building Bridges (CEOI17_building) C++14
100 / 100
 80 ms 12024 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2808 KB Output is correct
2 Correct 67 ms 2808 KB Output is correct
3 Correct 66 ms 2936 KB Output is correct
4 Correct 63 ms 2816 KB Output is correct
5 Correct 57 ms 4600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 66 ms 2808 KB Output is correct
7 Correct 67 ms 2808 KB Output is correct
8 Correct 66 ms 2936 KB Output is correct
9 Correct 63 ms 2816 KB Output is correct
10 Correct 57 ms 4600 KB Output is correct
11 Correct 63 ms 2680 KB Output is correct
12 Correct 66 ms 2816 KB Output is correct
13 Correct 51 ms 2688 KB Output is correct
14 Correct 66 ms 2816 KB Output is correct
15 Correct 80 ms 12024 KB Output is correct
16 Correct 55 ms 4600 KB Output is correct
17 Correct 29 ms 2688 KB Output is correct
18 Correct 31 ms 2688 KB Output is correct