Submission #1245873

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245873		kiennguyendinh	Building Bridges (CEOI17_building)	C++20	0 / 100	37 ms	32840 KiB

building

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,sum;
int dp[N];
array<int,2>a[N];
struct Line{
    int a,b;
    
    int calc(int x) {return a*x + b;}
    int slope() { return a;}
};
struct Lichao{
    Line tr[4000001];
    void build(){for(int i = 0; i < 4000001; ++i)
        tr[i] = {0, (int)1e18};}
    void update(Line f,int id,int l,int r){
        if(l == r){
            if(f.calc(l) < tr[id].calc(l)) tr[id] = f;
            return;
        }
        int mid = (l + r) >> 1;
        if(f.calc(mid) < tr[id].calc(mid)) swap(f,tr[id]);
        if(f.slope() > tr[id].slope()) update(f,id << 1,l,mid);
        if(f.slope() < tr[id].slope()) update(f,id << 1 | 1,mid + 1,r);
    }
    int query(int id,int l,int r,int pos){
        int cur = tr[id].calc(pos);
        int mid = (l + r) >> 1;
        if(mid == pos || l == r) return cur;
        if(mid < pos)
            return min(cur,query(id << 1 | 1,mid + 1,r,pos));
        return min(cur,query(id << 1,l,mid,pos));
    }
};
Lichao lc;
int main()
{
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++)cin>>a[i][0];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i][1];
        sum+=a[i][1];
    }
    lc.build();
    dp[1]=-a[1][1];
    Line init;
    init.a=-2*a[1][0];
    init.b=dp[1]+a[1][0]*a[1][0];
    lc.update(init,1,1,1000000);
    for(int i=2;i<=n;i++)
    {
        int x=lc.query(1,1,1000000,a[i][0]);
        dp[i]=x-a[i][1]+a[i][0]*a[i][0];
        Line ne;
        ne.a=-2*a[i][0];
        ne.b=dp[i]+a[i][0]*a[i][0];
        lc.update(ne,1,1,1000000);
    }
    cout<<dp[n]+sum;
    return 0;
}

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