Submission #1281132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281132		maithedung	Building Bridges (CEOI17_building)	C++20	100 / 100	63 ms	66216 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fast ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define exit return 0
#define cap pair<int,int>
#define fi first
#define se second
#define pb push_back
#define FOR(i,l,r) for(int i=l;i<=r;i++)
#define FOD(i,r,l) for(int i=r;i>=l;i--)
#define fill(f,x) memset(f,x,sizeof(f))
#define lcm(a,b) (a/__gcd(a,b)*b)
#define TIME 1.0 * clock() / CLOCKS_PER_SEC
int n;
int H[1000005];
int W[1000005];
int prefix[1000005];
int dp[1000005];
int inf=1e18;
struct line
{
    int a,b;
    line()
    {
        a=0;
        b=inf;
    }
    line(int a, int b): a(a),b(b) {}
    int slope()
    {
        return a;
    }
    int get(int x)
    {
        return a*x+b;
    }
};

line t[4000005];
void update(int id, int l, int r, line f)
{
    if(l==r)
    {
        if(f.get(l)<t[id].get(l)) t[id]=f;
        return;
    }
    int mid=(l+r)>>1;
    if(f.get(mid)<t[id].get(mid)) swap(t[id],f);
    if(f.get(l)<t[id].get(l))
    {
        update(id<<1,l,mid,f);
    }
    else update(id<<1|1,mid+1,r,f);
}

int get(int id, int l, int r, int pos)
{
    int cur=t[id].get(pos);
    if(l==r) return cur;
    int mid=(l+r)>>1;
    if(pos<=mid) return min(cur,get(id<<1,l,mid,pos));
    else return min(cur,get(id<<1|1,mid+1,r,pos));
}
signed main()
{
    fast;
    cin>>n;
    FOR(i,1,n) cin>>H[i];
    FOR(i,1,n) cin>>W[i];
    FOR(i,1,n)
    {
        prefix[i]=prefix[i-1]+W[i];
    }
    int m=*max_element(H+1,H+1+n);
    dp[1]=0;
    update(1,1,m,line(-2*H[1],dp[1]+H[1]*H[1]-prefix[1]));
    FOR(i,2,n)
    {
        dp[i]=get(1,1,m,H[i])+H[i]*H[i]+prefix[i]-W[i];
        update(1,1,m,line(-2*H[i],dp[i]+H[i]*H[i]-prefix[i]));
    }
    cout<<dp[n];
    exit;
}
/*
░▒▓███████▓▒░░▒▓█▓▒░░▒▓█▓▒░▒▓███████▓▒░ ░▒▓██████▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒▒▓███▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░▒▓█▓▒░░▒▓█▓▒░
░▒▓███████▓▒░ ░▒▓██████▓▒░░▒▓█▓▒░░▒▓█▓▒░░▒▓██████▓▒░


*/

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