Submission #940839

#	Time	Username	Problem	Language	Result	Execution time	Memory
940839		vivo2006	Building Bridges (CEOI17_building)	C++14	0 / 100	49 ms	8620 KiB

building

#include<iostream>
#include<cstring>

#define MAXN 100001

using namespace std;

long long n, total, h[MAXN], w[MAXN], cur, dp[MAXN];

struct Line
{
    long long m, b;
    Line() {}
    Line(long long _m, long long _b)
    {
        m = _m;
        b = _b;
    }
    long long operator() (long long x)
    {
        return m * x + b;
    }
    long long intersect(Line other)
    {
        return (b - other.b) / (other.m - m);
    }
};
struct LiChao
{
    Line arr[40 * MAXN];
    bool used[40 * MAXN];
    LiChao()
    {
        memset(used, 0, sizeof used);
    }
    void add(int ind, int l, int r, Line seg)
    {
        if(!used[ind])
        {
            used[ind] = 1;
            arr[ind] = seg;
            //cout<<l<<" "<<r<<": "<<seg.m<<" "<<seg.b<<endl;
            return;
        }
        if(arr[ind](l) < seg(l) && arr[ind](r) < seg(r))
        {
            arr[ind] = seg;
            //cout<<l<<" "<<r<<": "<<seg.m<<" "<<seg.b<<endl;
            return ;
        }
        if(arr[ind](l) >= seg(l) && arr[ind](r) >= seg(r))
        {
            return ;
        }
        int mid = (l + r) / 2;
        if(arr[ind](l) < seg(l)) swap(arr[ind], seg);
        if(arr[ind](mid) < seg(mid))
        {
            swap(arr[ind], seg);
            add(ind * 2 + 1, l, mid, seg);
        }
        else
        {
            add(ind * 2 + 2, mid + 1, r, seg);
        }
    }
    long long query(int ind, int l, int r, int x)
    {
        if(l == r)
        {
            if(used[ind]) return arr[ind](x);
            else return 1e18;
        }
        int mid = (l + r) / 2;
        long long ans = arr[ind](x);
        if(!used[ind]) ans = 1e18;
        if(x <= mid) return min(ans, query(ind * 2 + 1, l, mid, x));
        else return min(ans, query(ind * 2 + 2, mid + 1, r, x));
    }
}tree;
void read()
{
    cin>>n;
    for(int i = 0; i < n; i ++)
    {
        cin>>h[i];
    }
    for(int i = 0; i < n; i ++)
    {
        cin>>w[i];
        total += w[i];
    }
}
void solve()
{
    cur = 0;
    tree.add(0, 0, 1e6 + 1, Line(-2 * h[0], h[0] * h[0] + cur));
    for(int i = 1; i < n; i ++)
    {
        cur = tree.query(0, 0, 1e6 + 1, h[i]) - w[i] + h[i] * h[i];
        //cout<<cur<<": "<<tree.query(0, 0, 1e6 + 1, h[i])<<" "<<-w[i]<<" "<<h[i]<<endl;
        tree.add(0, 0, 1e6 + 1, Line(-2 * h[i], cur + h[i] * h[i]));
    }
    cout<<cur + total<<endl;
}
int main()
{
    read();
    solve();
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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