Submission #886636

#	Time	Username	Problem	Language	Result	Execution time	Memory
886636		dwuy	Building Bridges (CEOI17_building)	C++14	100 / 100	111 ms	15656 KiB

building

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 200005;

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 m < other.m;
        const Line *nxt = succ();
        if(!nxt) return 0;
        int x = other.m;
        return b - nxt->b < (nxt->m - m)*x;
    }
};

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 = -line.m;
        line.b = -line.b;
        auto itr = insert(line);
        itr->succ = [ = ]{ return next(itr) == end()? 0 : &*next(itr); };
        if(bad(itr)){
            erase(itr);
            return;
        }
        while(next(itr)!=end() && bad(next(itr))) erase(next(itr));
        while(itr!=begin() && bad(prev(itr))) erase(prev(itr));
    }

    int get(int x){
        if(empty()) return 0;
        auto itr = lower_bound(Line(x, OO));
        return itr->m*x + itr->b;
    }
};

int n;
int h[MX];
int w[MX];
int f[MX];
int sum[MX];

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

void solve(){
    Line_Container cht;
    cht.add(Line(-2*h[1], h[1]*h[1] - sum[1]));
    for(int i=2; i<=n; i++){
        f[i] = -cht.get(h[i]) + h[i]*h[i] + sum[i-1];
        cht.add(Line(-2*h[i], f[i] + h[i]*h[i] - sum[i]));
    }
    cout << f[n];
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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