oj.uz

답안 #62651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
62651 2018-07-29T16:14:27 Z Nnandi Building Bridges (CEOI17_building) C++14
100 / 100
 1491 ms 19776 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 < tab.size() && ch[0].a == tab[it].a) { it++; };
        if(it >= tab.size())  {
            ch.resize(1);
            swap(tab,ch); return;
        }
        ch[1] = tab[it]; it++;
        ll hm = 1;
        for(;it<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<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;
}

Compilation message

building.cpp: In member function 'void Burok::Order()':
building.cpp:43:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ll it = 1; while(it < tab.size() && ch[0].a == tab[it].a) { it++; };
                          ~~~^~~~~~~~~~~~
building.cpp:44:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(it >= tab.size())  {
            ~~~^~~~~~~~~~~~~
building.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(;it<tab.size();it++) {
              ~~^~~~~~~~~~~
building.cpp:67:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(ll i=0;i<tab.size()-1;i++) {
                    ~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 4 ms 764 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1491 ms 7312 KB Output is correct
2 Correct 1463 ms 8272 KB Output is correct
3 Correct 1367 ms 9408 KB Output is correct
4 Correct 1330 ms 10304 KB Output is correct
5 Correct 572 ms 11244 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 4 ms 764 KB Output is correct
6 Correct 1491 ms 7312 KB Output is correct
7 Correct 1463 ms 8272 KB Output is correct
8 Correct 1367 ms 9408 KB Output is correct
9 Correct 1330 ms 10304 KB Output is correct
10 Correct 572 ms 11244 KB Output is correct
11 Correct 1184 ms 12460 KB Output is correct
12 Correct 1402 ms 13488 KB Output is correct
13 Correct 443 ms 14716 KB Output is correct
14 Correct 1383 ms 15856 KB Output is correct
15 Correct 609 ms 16748 KB Output is correct
16 Correct 519 ms 17488 KB Output is correct
17 Correct 105 ms 18532 KB Output is correct
18 Correct 173 ms 19776 KB Output is correct