제출 #1275243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1275243		danglayloi1	Building Bridges (CEOI17_building)	C++20	100 / 100	38 ms	18384 KiB

building

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e5+5;
struct dak
{
    ll a, b;
    dak() : a(0), b(0) {}
    dak(ll a, ll b) : a(a), b(b) {}
    ll cal(ll x)
    {
        return a*x+b;
    }
};
struct lichao
{
    vector<dak> nod;
    lichao() {}
    lichao(int sz) : nod(sz+5, dak(0, inf)) {}
    void update(int l, int r, dak f)
    {
        if(l>r) return;
        int mid=(l+r)>>1;
        if(l==r)
        {
            nod[mid]=(f.cal(l)<nod[mid].cal(l)?f:nod[mid]);
            return;
        }
        if(f.cal(mid)<nod[mid].cal(mid)) swap(nod[mid], f);
        if(f.a>nod[mid].a)
            update(l, mid-1, f);
        if(f.a<nod[mid].a)
            update(mid+1, r, f);
    }
    ll get(int l, int r, int p)
    {
        int mid=(l+r)>>1;
        ll cur=nod[mid].cal(p);
        if(l==r) return cur;
        if(p==mid) return cur;
        if(p<=mid) return min(cur, get(l, mid-1, p));
        return min(cur, get(mid+1, r, p));
    }
};
int n;
ll h[nx], a[nx], dp[nx], mx=0;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>h[i], mx=max(mx, h[i]);
    for(int i = 1; i <= n; i++)
        cin>>a[i], a[i]+=a[i-1];
    memset(dp, -0x3f, sizeof(dp));
    dp[1]=0;
    lichao st(mx);
    for(int i = 1; i <= n; i++)
    {
        if(i>1)
        {
            dp[i]=st.get(0, mx, h[i])+a[i-1]+h[i]*h[i];
        }
        st.update(0, mx, dak(-2ll*h[i], dp[i]-a[i]+h[i]*h[i]));
    }
    cout<<dp[n];
}

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