Submission #1314158

#TimeUsernameProblemLanguageResultExecution timeMemory
1314158anngelaBuilding Bridges (CEOI17_building)C++20
100 / 100
43 ms9756 KiB
#include <set>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;

using ll = long long;
const int MAXN = 1e5 + 5;
const ll INF  = 1e18 + 5;
ll n, h[MAXN], w[MAXN];
ll dp[MAXN];
ll sp[MAXN];

void Read()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> h[i];
    for (int i = 1; i <= n; ++i)
    {
        cin >> w[i];
        sp[i] = sp[i - 1] + w[i];
    }
}

struct Line {
    ll m, k; // m*x + k
    mutable ll x;

    bool operator < (const Line &other) const { return m > other.m; } // aici < pt maxim
    bool operator < (int x) const { return this->x < x; } 
    ll operator()(ll x) const {return m * x + k;}
};

struct CHT : multiset<Line, less<>> {
    static const ll INF = LLONG_MAX;

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

    bool isect(iterator a, iterator b)
    {
        if (b == end()) {a->x = INF; return false;}
        if (a->m == b->m) 
			a->x = (a->k < b->k ? INF : -INF); // aici invers pt maxim
        else 
			a->x = div(b->k - a->k, a->m - b->m);
        return a->x >= b->x;
    }

    void add(ll m, ll k)
    {
        auto c = insert({m, k, 0}), b = c++, a = b;
		while (isect(b, c))
			c = erase(c);
		
		if (a != begin() && isect(--a, b))
			isect(a, b = erase(b));
			
		while ((b = a) != begin() && (--a)->x >= b->x)
			isect(a, erase(b));
    }

    ll query(ll x)
    {
        Line line = *lower_bound(x);
        return line(x);
    }
};

void Solve()
{
    CHT hull;
    
    fill(dp + 1, dp + n + 1, INF);
    dp[1] = 0;
    for (int i = 1; i <= n; ++i)
    {
		if (i > 1) 
			dp[i] = hull.query(h[i]) + h[i] * h[i] + sp[i - 1];
        hull.add(-2 * h[i], dp[i] + h[i] * h[i] - sp[i]);
    }

    cout << dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	Read();
    Solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...