Submission #1246371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246371		kiennguyendinh	Building Bridges (CEOI17_building)	C++20	30 / 100	93 ms	127816 KiB

building

#include <bits/stdc++.h>
using namespace std;
struct Line{
    long long a,b;
    long double p;
    long long slope() {return a;}
    long long calc(long long x) {return a*x + b;}
    bool operator < (const Line &o){
        return (a == o.a)? (b < o.b) : (a > o.a);
    }
    bool operator < (long long x) {return p < x;}
};
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);
    }
    long long query(int id,int l,int r,int pos){
        long long 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 n;
long long a[100001][2],dp[100001],w[100001],sum = 0;
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: 30 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40