Submission #119389

#	Time	Username	Problem	Language	Result	Execution time	Memory
119389		zubec	Building Bridges (CEOI17_building)	C++14	100 / 100	160 ms	12920 KiB

building

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

const int N = 100100;

int n;

ll h[N], w[N], dp[N];

const ld Fictive = 5e18;

struct line{
    ld k, b;
    set<line>::iterator it;
    line (ld _k, ld _b){
        k = _k;
        b = _b;
    }
    ld eval(ld x){
        return k*x+b;
    }
};
set<line> lineSet;

const bool operator < (const line& fi, const line& se){
    if (se.k == Fictive){
        auto it = fi.it;
        return next(it) != lineSet.end() && next(it)->k*se.b+next(it)->b >= it->k*se.b+it->b;
    }
    return fi.k > se.k || (fi.k == se.k && fi.b > se.b);
}

inline ld intersect(line l1, line l2){
    return (l1.b-l2.b)/(l2.k-l1.k);
}

inline bool to_erase(line fi, line se, line th){
    ld x = intersect(fi, th);
    return se.eval(x) <= th.eval(x);
}


void add(line l){
    l.k *= -1;
    l.b *= -1;
    auto it = lineSet.insert(l).first;
    line* pntr = (line*)&*it;
    pntr->it = it;
    if (it != lineSet.begin() && prev(it)->k == it->k){
        lineSet.erase(it);
        return;
    }
    if (next(it) != lineSet.end() && it->k == next(it)->k){
        lineSet.erase(next(it));
    }
    if (it != lineSet.begin() && next(it) != lineSet.end() && to_erase(*prev(it), *it, *next(it))){
        lineSet.erase(it);
        return;
    }
    while(it != lineSet.begin() && prev(it) != lineSet.begin() && to_erase(*prev(prev(it)), *prev(it), *it)){
        lineSet.erase(prev(it));
    }
    while(next(it) != lineSet.end() && next(next(it)) != lineSet.end() && to_erase(*it, *next(it), *next(next(it)))){
        lineSet.erase(next(it));
    }
}

ld get(ld x){
    line gt = *lineSet.lower_bound(line(Fictive, x));
    return -gt.eval(x);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++){
        ll p;
        cin >> p;
        w[i] = w[i-1] + p;
    }


    /*for (int i = 2; i <= n; i++){
        dp[i] = 1e18;
        for (int j = 1; j < i; j++){
            dp[i] = min(dp[i], dp[j] + w[i-1]-w[j] + (h[i]-h[j])*(h[i]-h[j]));
        }
        //cout << i << ' ' << dp[i] << endl;
    }*/
    //cout << endl;
    for (int i = 1; i <= n; i++){
        if (i != 1){
            dp[i] = get(h[i])+h[i]*h[i]+w[i-1];
        }
        //cout << i << ' ' << dp[i] << endl;
        add({-2*h[i], dp[i] - w[i] + h[i]*h[i]});
    }
    cout << dp[n];

}

Compilation message (stderr)

building.cpp: In function 'int main()':
building.cpp:102:16: warning: narrowing conversion of '(-2 * h[i])' from 'll {aka long long int}' to 'ld {aka long double}' inside { } [-Wnarrowing]
         add({-2*h[i], dp[i] - w[i] + h[i]*h[i]});
              ~~^~~~~
building.cpp:102:36: warning: narrowing conversion of '((dp[i] - w[i]) + (h[i] * h[i]))' from 'll {aka long long int}' to 'ld {aka long double}' inside { } [-Wnarrowing]
         add({-2*h[i], dp[i] - w[i] + h[i]*h[i]});
                       ~~~~~~~~~~~~~^~~~~~~~~~~

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