제출 #561196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
561196		fatemetmhr	Building Bridges (CEOI17_building)	C++17	0 / 100	868 ms	12316 KiB

building

#include <bits/stdc++.h>

using namespace std;

typedef long long    ll;
typedef pair<ll, ll> pll;

#define pb      push_back
#define all(x)  x.begin(), x.end()
#define fi      first
#define se      second
#define mp      make_pair

const int maxn5 = 1e5 + 10;
const int ssq   = 320;
const ll  inf   = 1e18;


struct _cht{
    int pt;
    pair <ll, pll> a[maxn5]; // {st, {const, shib}}
    void clear(){
        pt = 0;
    }

    ll inter(pll a, pll b){ // az koja b akidan behtar hast?
        if(a.se == b.se)
            return (a.fi > b.fi ? inf : -inf);
        return (a.fi - b.fi) / (b.se - a.se) + ((a.fi - b.fi) % (b.se - a.se) > 0);
    }

    void add(pll x){
        while(pt && inter(a[pt].se, x) <= a[pt].fi)
            pt--;
        a[pt] = mp(-inf, x);
        if(pt)
            a[pt].fi = inter(a[pt].se, x);
        pt++;
    }

    ll get_max(ll x){
        int id = upper_bound(a, a + pt, mp(x, mp(inf, inf))) - a - 1;
        return a[id].se.fi + a[id].se.se * x;
    }

} cht;

ll h[maxn5], w[maxn5];
ll dp[maxn5];
set <pair<ll, int>> av;

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

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

    cht.clear();

    for(int i = 0; i < n; i += ssq){
        for(int j = max(i, 1); j < n && j < i + ssq; j++){
            dp[j] = inf;
            if(cht.pt){
                dp[j] = cht.get_max(h[j]) * -1 + w[j - 1] + ll(h[j]) * h[j];
            }
            for(int k = i; k < j; k++)
                dp[j] = min(dp[j], dp[k] + w[j - 1] - w[k] + h[k] * h[k] + h[j] * h[j] - 2 * h[j] * h[k]);
            av.insert({h[j], j});
        }
        cht.clear();
        for(auto it = av.begin(); it != av.end(); it++){
            int v = (it -> se);
            cht.add({w[v] - dp[v] - h[v] * h[v], 2 * h[v]}); // {const, shib}
        }
    }

    cout << dp[n - 1] << endl;
}

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