Submission #62652

#	Time	Username	Problem	Language	Result	Execution time	Memory
62652		Nnandi	Building Bridges (CEOI17_building)	C++14	100 / 100	1556 ms	6376 KiB

building

#include <bits/stdc++.h>
#define INF 100000000000000000.0
using namespace std;

typedef long long ll;

struct Line {
    ll a, b; // Y = aX + b
    double kp, vp;
    Line() {}
    Line(ll aa, ll bb) {
        a = aa;
        b = bb;
    }
    const bool operator< (Line masik) const {
        if(a != masik.a) return a > masik.a;
        return b < masik.b;
    }
};

double cross(Line e, Line f) {
    return (double)(f.b - e.b) / (double)(e.a - f.a);
}

struct Burok {
    vector<Line> tab;
    bool ord;
    Burok() {
        tab.resize(0);
        ord = false;
    }
    void Add_Line(ll a, ll b) {
        ord = false;
        Line uj(a,b);
        tab.push_back(uj);
    }
    void Order() {
        ord = true;
        sort(tab.begin(),tab.end());
        if(tab.size()==1) return;
        vector<Line> ch(tab.size());
        ch[0] = tab[0];
        ll it = 1; while(it < (ll)tab.size() && ch[0].a == tab[it].a) { it++; };
        if(it >= (ll)tab.size())  {
            ch.resize(1);
            swap(tab,ch); return;
        }
        ch[1] = tab[it]; it++;
        ll hm = 1;
        for(;it<(ll)tab.size();it++) {
            if(tab[it].a == ch[hm].a) continue;
            bool kell = true;
            while(hm >= 1 && kell) {
                double ez = cross(ch[hm-1],tab[it]);
                double az = cross(ch[hm-1],ch[hm]);
                if(ez <= az) { //!!!!!!
                    hm--;
                }
                else {
                    kell = false;
                }
            }
            ch[hm+1] = tab[it]; hm++;
        }
        ch.resize(hm+1);
        swap(tab,ch);
        for(ll i=0;i<(ll)tab.size()-1;i++) {
            tab[i].vp = cross(tab[i],tab[i+1]);
            tab[i+1].kp = cross(tab[i+1],tab[i]);
        }
        tab[0].kp = -INF;
        tab[hm].vp = INF;
        return;
    }
    ll Get_Min_Value(ll x) {
        if(tab.size() == 0) return (ll)INF;
        if(!ord) {
            ll min_val(tab[0].a * x + tab[0].b);
            for(Line d:tab) {
                min_val = min(min_val,d.a * x + d.b);
            }
            return min_val;
        }
        else {
            ll b1 = 0;
            ll b2 = tab.size()-1;
            while(b1 < b2) {
                ll mid = (b1 + b2) / 2;
                if(tab[mid].kp <= (double)x && (double)x <=tab[mid].vp) {
                    b1 = mid;
                    b2 = mid;
                }
                else if(tab[mid].kp > (double)x) {
                    b2 = mid-1;
                }
                else {
                    b1 = mid+1;
                }
            }
            return x * tab[b1].a + tab[b1].b;
        }
    }
};

ll n;
const ll maxn = 100005;
ll h[maxn], w[maxn];

Burok data[400];
ll suf_sum[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(ll i=0;i<n;i++) {
        cin>>h[i];
    }
    for(ll i=0;i<n;i++) {
        cin>>w[i];
    }
    suf_sum[n] = 0;
    for(ll i=n-1;i>=0;i--) {
        suf_sum[i] = suf_sum[i+1] + w[i];
    }
    ll g = (ll)sqrt(n);
    for(ll i=0;i<n;i++) {
        if(i == 0) {
            data[i/g].Add_Line(-2*h[i],h[i]*h[i] + suf_sum[i+1]);
        }
        else {
            ll min_pre_cost = (ll) INF;
            for(ll j=0;j<=i/g;j++) {
                min_pre_cost = min(min_pre_cost, data[j].Get_Min_Value(h[i]));
            }
            ll cost = min_pre_cost + h[i]*h[i] - suf_sum[i];
            if(i == n-1) {
                cout<<cost<<endl;
                return 0;
            }
            data[i/g].Add_Line(-2*h[i],cost + suf_sum[i+1] + h[i]*h[i]);
        }
        if((i+1) % g == 0) {
            data[i/g].Order();
        }
    }
    return 0;
}

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