Submission #1139078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139078		btninh	Building Bridges (CEOI17_building)	C++20	0 / 100	53 ms	64580 KiB

building

#include <bits/stdc++.h>

#define ll long long
#define int long long
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int>
#define INF 1e18
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define TASK "test"

using namespace std;
const int N = 100005;
const int mod = 1e9 + 7;

int n, h[N], w[N];

struct Line{
    ll a, b;
    Line(ll a = 0, ll b = INF): a(a), b(b) {}
    ll calc(int x){
        return a * x + b;
    }
    ll sl(){
        return a;
    }
};
namespace lichao{

    vector<Line> t;
    void init(){
        t.resize(4000001, Line());
    }
    void ins(Line f, int id = 1, int l = 1, int r = 1e6){
        if (l == r){
            if (f.calc(l) < t[id].calc(l)){
                t[id] = f;
            }
            return;
        }
        int mid = (l + r) >> 1;
        if (f.calc(mid) < t[id].calc(mid)) swap(f, t[id]);
        if (f.sl() > t[id].sl()){
            ins(f, id << 1, l, mid);
        }
        else ins(f, id << 1 | 1, mid + 1, r);
    }

    ll get(ll x, int id = 1, int l = 1, int r = 1e6){
        int mid = (l + r) >> 1;
        ll cur = t[id].calc(x);
        if (l == r) return cur;
        if (x <= mid) return min(cur, get(x, id << 1, l, mid));
        return min(cur, get(x, id << 1 | 1, mid + 1, r));
    }

};

void Proc(){
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) {
        cin >> w[i];
        w[i] += w[i - 1];
    }
    //dp[i] = dp[j] + (h[i] - h[j])^2 + pre[i - 1] - pre[j]
    //dp[i] = - 2*h[j]*h[i] + dp[j] + h[j]*h[j] - pre[j] + h[i]*h[i] + pre[i - 1];
    lichao::init();
    lichao::ins(Line(-2 * h[1], h[1] * h[1] - w[1]));
    FOR(i, 2, n){
        ll val = lichao::get(h[i]) + h[i] * h[i] + w[i - 1];
        lichao::ins(Line(-2 * h[i], val + h[i] * h[i] - w[i]));
    }
    cout << lichao::get(h[n]) + h[n] * h[n] + w[n - 1];
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; T = 1;
    //cin >> T;
    while (T--) Proc();
}

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