Submission #132423

#	Time	Username	Problem	Language	Result	Execution time	Memory
132423		Vardanyan	Building Bridges (CEOI17_building)	C++14	60 / 100	68 ms	10488 KiB

building

#include <bits/stdc++.h>
using namespace std;
const int N = 1000*100+5;
long long dp[N];
long long a[N];
long long b[N];
long long pref[N];
const long long INF = 1e18;
struct line{
    long long k,b;
    line():k(0),b(0){}
    line(long long _k,long long _b):k(_k),b(_b){}
};
long long f(line ln,long long x){
    if(ln.k+ln.b == 0) return INF;
    long long u = ln.k*x+ln.b;
   // if(u<0 && ln.k>=0 && x>=0 && ln.b>=0) u = INF;
    return u;
}
struct node{
    node* l;
    node* r;
    line ln;
    node():l(NULL),r(NULL),ln(0,0){}
};
long long maxn = 1000*1000*2;
void add_line(node* v,line ln,long long l = -maxn,long long r = maxn){
    if(l>r) return;
    long long m = (l+r)/2;
    bool lef = f(ln,l)<f(v->ln,l);
    bool mid = f(ln,m)<f(v->ln,m);
    if(mid){
        swap(v->ln,ln);
    }
    if(lef!=mid){
        if(v->l == NULL) v->l = new node();
        add_line(v->l,ln,l,m);
    }
    else{
        if(v->r == NULL) v->r = new node();
        add_line(v->r,ln,m+1,r);
    }
}
long long get(node* v,long long x,long long l = -maxn,long long r = maxn){
    if(v == NULL || l>r) return INF;
    if(l == r){
        return f(v->ln,x);
    }
    long long m = (l+r)/2;
    if(f(v->ln,x)<f(v->ln,m)){
        return min(f(v->ln,x),get(v->l,x,l,m));
    }
    else{
        return min(f(v->ln,x),get(v->r,x,m+1,r));
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++) cin>>a[i];
    for(int i = 1;i<=n;i++){
        cin>>b[i];
        pref[i] = pref[i-1]+b[i];
       // dp[i] = INF;
    }
    dp[1] = 0;
    node* root = new node();
    add_line(root,line(a[1],dp[1]+a[1]*a[1]-pref[1]));
    for(int i = 2;i<=n;i++){
        /*for(int j = 1;j<i;j++){
            dp[i] = min(dp[i],dp[j]+(a[i]-a[j])*(a[i]-a[j])+pref[i-1]-pref[j]);
        }*/
        long long x = get(root,-2*a[i]);
        dp[i] = x+a[i]*a[i]+pref[i-1];
        add_line(root,line(a[i],dp[i]+a[i]*a[i]-pref[i]));
   //     cout<<dp[i]<<endl;
    }
    cout<<dp[n]<<endl;
    return 0;
}

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