Submission #869645

#	Time	Username	Problem	Language	Result	Execution time	Memory
869645		MON	Building Bridges (CEOI17_building)	C++17	100 / 100	84 ms	65872 KiB

building

#include<iostream>
using namespace std;
using ll = long long;

constexpr int CHAO = 1e6 + 1;

struct line
{
    int m; ll b;
    line(int a,ll c) : m(a),b(c) {}
    line() : m(0),b(1LL<<62) {}
    ll operator ()(int x){return 1LL * x * m + b;}
}li[CHAO * 4];

void baga(line f,int a = 1,int l = 0,int r = CHAO)
{
    if(l + 1 == r)
        {
            if(f(l) < li[a](l))
                swap(f,li[a]);
            return;
        }

    int mid = l + (r - l) / 2;
    if(f.m > li[a].m) swap(f,li[a]);
    if(f(mid) < li[a](mid)) swap(f,li[a]),baga(f,a<<1,l,mid);
    else baga(f,a<<1|1,mid,r);

}

ll get(int x,int a = 1 ,int l = 0 , int r = CHAO)
{
    if(l + 1 == r) return li[a](x);
    int mid = l + (r - l) / 2;
    if(x < mid) return min(li[a](x),get(x,a<<1,l,mid));
    return min(li[a](x),get(x,a<<1|1,mid,r));
}

int main()
{
    int n; cin >> n; int h[n + 1],w[n + 1];
    ll ans = 0; for(int i = 1; i <= n ; i++) cin >> h[i];
    for(int i = 1; i <= n ; i++) cin >> w[i],ans += w[i];
    ll dp[n + 1]; dp[1] = -w[1]; baga(line(-2 * h[1],1LL * h[1] * h[1] - w[1]));
    for(int i = 2; i <= n ; i++)
    {
        dp[i] = get(h[i]) + 1LL * h[i] * h[i] -w[i];
        baga(line(-2*h[i],1LL * h[i] * h[i] + dp[i]));
    }

    cout << ans + dp[n];
}

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