Submission #1344417

#TimeUsernameProblemLanguageResultExecution timeMemory
1344417huypham2009Building Bridges (CEOI17_building)C++20
100 / 100
40 ms7380 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long inf = 1e18;
const int maxn = 1e5 + 5;
struct line{
    long long a, b;
    line()
    {
        a = 0;
        b = inf;
    }
    long long operator () (long long x) const
    {
        return a * x + b;
    }
};
struct node{
    node *L, *R;
    line curl;
    node()
    {
        L = NULL;
        R = NULL;
        curl.b = inf;
    }
};
struct lichao{
    node *root;
    int ml = 0, mr = 1e6;
    lichao()
    {
        root = new node();
    }
    
    void update(node *&cur, int l, int r, line linex)
    {
        if(l > r) return;
        if(cur == NULL)
        {
            cur = new node();
        }
        int mid = (l + r) >> 1;
        if(cur -> curl(mid) > linex(mid)) swap(cur -> curl, linex);
        if(linex(mid) == inf) return;
        if(linex.a < cur -> curl.a) update(cur -> R, mid + 1, r, linex);
        else update(cur -> L, l, mid - 1, linex);
    }
    void update(line linex)
    {
        update(root, ml, mr, linex);
    }
    long long get(node *&cur, int l, int r, long long x)
    {
        if(l > r || cur == NULL) return inf;
        int mid = (l + r) >> 1;
        if(mid > x) return min(cur -> curl(x), get(cur -> L, l, mid - 1, x));
        else return min(cur -> curl(x), get(cur -> R, mid + 1, r, x));
    }
    long long get(long long x)
    {
        return get(root, ml, mr, x);
    }
} lct;
int n, h[maxn], pf[maxn];
long long dp[maxn];
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++)
    {
        cin >> pf[i];
        pf[i] += pf[i - 1];
    }
    line base;
    base.a = -2 * h[1];
    base.b = h[1] * h[1] - pf[1];
    lct.update(base);
    for(int i = 2; i <= n; i++)
    {
        line res;
        dp[i] = lct.get(h[i]) + h[i] * h[i] + pf[i - 1];
        res.a = -2 * h[i];
        res.b = h[i] * h[i] + dp[i] - pf[i];
        lct.update(res);
    }
    cout << dp[n];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...