Submission #898343

#	Time	Username	Problem	Language	Result	Execution time	Memory
898343		dwuy	Building Bridges (CEOI17_building)	C++14	100 / 100	85 ms	14768 KiB

building

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

const int OO = 1e18;

struct Line{
    int m, b;
    mutable function<const Line *()> succ;

    Line(int m=0, int b=OO){
        this->m = m;
        this->b = b;
    }

    bool operator < (const Line &other) const{
        if(other.b != OO) return this->m < other.m;
        auto nxt = succ();
        if(!nxt) return 0;
        return b - nxt->b < other.m*(nxt->m - m);
    }
};

struct Line_container : public multiset<Line>{
    bool bad(iterator cur){
        auto nxt = next(cur);
        if(cur == begin()){
            if(nxt==end()) return 0;
            return cur->m == nxt->m && cur->b == nxt->b;
        }
        auto pre = prev(cur);
        if(nxt == end()) return cur->m == pre->m && cur->b == pre->b;
        return (pre->b - cur->b)*(nxt->m - cur->m) >= (cur->b - nxt->b)*(cur->m - pre->m);
    }

    void add(Line line){
        line.m *= -1;
        line.b *= -1;
        auto cur = insert(line);
        cur->succ = [=] {return next(cur)==end()? 0 : &*next(cur);};
        if(bad(cur)){
            erase(cur);
            return;
        }
        while(next(cur)!=end() && bad(next(cur))) erase(next(cur));
        while(cur!=begin() && bad(prev(cur))) erase(prev(cur));
    }

    int get(int val){
        auto itr = lower_bound(Line(val));
        if(itr == end()) return 0;
        return val*itr->m + itr->b;
    }
};

const int MX = 200005;
int n;
int h[MX];
int c[MX];
int dp[MX];

void nhap(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1; i<=n; i++) cin >> c[i], c[i] += c[i-1];
}


int sqr(int x){
    return x*x;
}

/// h[i]^2 + h[j]^2 - 2*h[i]*h[j] + dp[j] + c[i-1] - c[j];

void solve(){
    dp[1] = 0;
    Line_container cht;
    cht.add(Line(-2*h[1], sqr(h[1]) - c[1]));
    for(int i=2; i<=n; i++){
        dp[i] = -cht.get(h[i]) + sqr(h[i]) + c[i-1];
        cht.add(Line(-2*h[i], sqr(h[i]) + dp[i] - c[i]));
    }
    cout << dp[n];
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    nhap();
    solve();

    return 0;
}
/**

6
3 8 7 1 6 6
0 -1 9 1 2 0

0 25 15

-6 + 9
-16 + 90
-14 + 56



**/

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