oj.uz

Submission #62652

# Submission time Handle Problem Language Result Execution time Memory
62652 2018-07-29T16:16:26 Z Nnandi Building Bridges (CEOI17_building) C++14
100 / 100
 1556 ms 6376 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 3 ms 664 KB Output is correct
5 Correct 4 ms 728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1549 ms 6180 KB Output is correct
2 Correct 1531 ms 6180 KB Output is correct
3 Correct 1556 ms 6248 KB Output is correct
4 Correct 1340 ms 6248 KB Output is correct
5 Correct 483 ms 6248 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 3 ms 664 KB Output is correct
5 Correct 4 ms 728 KB Output is correct
6 Correct 1549 ms 6180 KB Output is correct
7 Correct 1531 ms 6180 KB Output is correct
8 Correct 1556 ms 6248 KB Output is correct
9 Correct 1340 ms 6248 KB Output is correct
10 Correct 483 ms 6248 KB Output is correct
11 Correct 1224 ms 6248 KB Output is correct
12 Correct 1389 ms 6248 KB Output is correct
13 Correct 361 ms 6248 KB Output is correct
14 Correct 1284 ms 6376 KB Output is correct
15 Correct 648 ms 6376 KB Output is correct
16 Correct 606 ms 6376 KB Output is correct
17 Correct 103 ms 6376 KB Output is correct
18 Correct 131 ms 6376 KB Output is correct