Submission #171609

#	Time	Username	Problem	Language	Result	Execution time	Memory
171609		nicolaalexandra	Building Bridges (CEOI17_building)	C++14	0 / 100	125 ms	7520 KiB

building

#include <bits/stdc++.h>
#define DIM 100010
#define DIMM 1000010
#define INF 1000000000000000000LL
using namespace std;

pair <long long,long long> aint[DIMM*4];
long long h[DIM],w[DIM],sp[DIM],dp[DIM];
long long n,i;
long long maxi;
long long f (long long a, long long b, long long x){
    return a*x+b;
}
void add (long long nod, long long st, long long dr, long long a, long long b){
    if (st == dr){
        if (f(a,b,st) < f(aint[nod].first,aint[nod].second,st))
            aint[nod] = make_pair (a,b);
        return;
    }
    long long mid = (st+dr)>>1;
    int ok_mid = 0, ok_dr = 0;
    if (f(a,b,mid) < f(aint[nod].first,aint[nod].second,mid))
        ok_mid = 1;
    if (f(a,b,dr) < f(aint[nod].first,aint[nod].second,dr))
        ok_dr = 1;
    if (!ok_mid && !ok_dr) /// ma duc in stanga
        add (nod<<1,st,mid,a,b);
    else {
        if (!ok_mid && ok_dr)
            add ((nod<<1)|1,mid+1,dr,a,b);
        else {
            /// inseamna ca ok_mid = 1
            swap (aint[nod].first,a);
            swap (aint[nod].second,b);
            if (ok_dr)
                add (nod<<1,st,mid,a,b);
            else add ((nod<<1)|1,mid+1,dr,a,b);
        }
    }
}
long long query (long long nod, long long st, long long dr, long long x){
    if (st == dr)
        return f(aint[nod].first,aint[nod].second,x);

    long long mid = (st+dr)>>1;
    long long sol = INF;
    if (x <= mid)
        sol = query (nod<<1,st,mid,x);
    else sol = query ((nod<<1)|1,mid+1,dr,x);
    return min (sol,f(aint[nod].first,aint[nod].second,x));
}
void init (long long nod, long long st, long long dr){
    aint[nod] = make_pair(INF,INF);
    if (st == dr)
        return;
    long long mid = (st+dr)>>1;
    init (nod<<1,st,mid);
    init ((nod<<1)|1,mid+1,dr);
}
int main (){

    cin>>n;
    for (i=1;i<=n;i++){
        cin>>h[i];
        maxi = max (maxi,h[i]);
    }
    for (i=1;i<=n;i++){
        cin>>w[i];
        sp[i] = sp[i-1] + w[i];
    }
    /// pe primul si ultimul le iau obligatoriu
    /// dp[i] - costul minim sa ajung in i
    //for (i=2;i<=n;i++)
      //  dp[i] = (h[i]-h[1])*(h[i]-h[1]) + sp[i-1]-sp[1];
    init (1,0,maxi);
    add (1,0,maxi,-2*h[1],h[1]*h[1]-w[1]);
    for (i=2;i<=n;i++){
        dp[i] = h[i]*h[i] + sp[i-1] + query (1,0,maxi,h[i]);
        add (1,0,maxi,-2*h[i],dp[i]+h[i]*h[i]-sp[i]);
    }
    cout<<dp[n];

    return 0;
}

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