Submission #1001058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001058		nngan267	Building Bridges (CEOI17_building)	C++17	100 / 100	80 ms	12880 KiB

building

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

#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pll pair<ll, ll>
#define vi vector<int>
#define db long double

const int maxn = 1e5+5;
const ll mod = 1e9+7;
const ll inf = 1e18+7;
const double eps = 1e-9;
const double pi = acos(-1);
const int block_size = 320;

int n, h[maxn], w[maxn];
ll s[maxn];
ll dp[maxn];

struct Line{
    bool t;
    db x;
    ll a, b;

    bool operator < (const Line &l) const{
        if(t || l.t) return x < l.x;
        return a > l.a;
    }
};

struct linecontainer{
    set<Line> cht;

    bool has_prev(set<Line>::iterator it) {return it != cht.begin();}
    bool has_next(set<Line>::iterator it) {return it != cht.end() && next(it) != cht.end();}

    db intersect(set<Line>::iterator l1, set<Line>::iterator l2){
        return (double) (l2->b - l1->b) / (l1->a - l2->a);
    }

    void cal_x(set<Line>::iterator it){
        if(has_prev(it)){
            Line l = *it;
            l.x = intersect(prev(it), it);
            cht.insert(cht.erase(it), l);
        }
    }

    bool bad(set<Line>::iterator it){
        return has_prev(it) && has_next(it) && (intersect(prev(it), next(it)) <= intersect(prev(it), it));
    }

    void add(ll a, ll b){
        set<Line>::iterator it;
        it = cht.lower_bound({0, 0, a, b});
        if(it != cht.end() && it->a == a){
            if(it->b >= b) cht.erase(it);
            else return;
        }
        it = cht.insert({0, 0, a, b}).first;
        if(bad(it)) cht.erase(it);
        else{
            while(has_prev(it) && bad(prev(it))) cht.erase(prev(it));
            while(has_next(it) && bad(next(it))) cht.erase(next(it));
            if(has_next(it)) cal_x(next(it));
            cal_x(it);
        }
    }

    ll query(ll x){
        Line l = *prev(cht.upper_bound({1, (double)x, 0, 0}));
        return l.a * x + l.b;
    }
};

void solve(){
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> h[i];
    }
    for(int i=1; i<=n; i++){
        cin >> w[i];
        s[i] = s[i-1] + w[i];
    }
    linecontainer cht;
    ll a = -2*h[1];
    ll b = 1ll*h[1]*h[1] - s[1];
    cht.add(a, b);
    for(int i=2; i<=n; i++){
        dp[i] = cht.query(h[i]) + 1ll*h[i]*h[i] + s[i-1];
        a = -2*h[i];
        b = dp[i] + 1ll*h[i]*h[i] - s[i];
        cht.add(a, b);
    }
    cout << dp[n] << "\n";
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
//    cin >> test;
    while(test--){
        solve();
    }
}

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