Submission #940859

#	Time	Username	Problem	Language	Result	Execution time	Memory
940859		vivo2006	Building Bridges (CEOI17_building)	C++17	100 / 100	81 ms	66548 KiB

building

#include<iostream>
#include<cstring>

#define MAXN 100001
#define int long long

using namespace std;

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

struct Line
{
    long long m, b;
    Line() {m = b = 1e12 + 10;}
    Line(long long _m, long long _b)
    {
        m = _m;
        b = _b;
    }
    long long operator() (long long x)
    {
        return m * x + b;
    }
};
struct LiChao
{
    Line arr[40 * MAXN];
    void add(int ind, int l, int r, Line seg)
    {
        if(l == r)
        {
            if(arr[ind](l) > seg(l))
            {
                arr[ind] = seg;
            }
           return;
        }
        int mid = (l + r) / 2;
        if(seg.m > arr[ind].m) 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)
        {
            return arr[ind](x);
        }
        int mid = (l + r) / 2;
        long long ans = arr[ind](x);
        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 = -w[0];
    tree.add(0, 0, 1e6 + 10, Line(-2 * h[0], h[0] * h[0] + cur));
    for(int i = 1; i < n; i ++)
    {
        cur = tree.query(0, 0, 1e6 + 10, 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 + 10, Line(-2 * h[i], cur + h[i] * h[i]));
    }
    cout<<cur + total<<endl;
}
signed main()
{
    read();
    solve();
    return 0;
}
/*
6
3 8 7 1 6 6
0 -1 9 1 2 0
*/

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