Submission #1275555

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275555		Thunnus	Building Bridges (CEOI17_building)	C++20	0 / 100	55 ms	66020 KiB

building

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define  vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()                      

const int MAXH = 1e6 + 5;

struct Line{
    int m, c;
    Line(int m, int c) : m(m), c(c) {}
    Line() : Line(INT32_MAX, INT32_MAX) {}
    
    inline int eval(int x){
        return m * x + c;
    }
};

struct LiChao{
    int n;
    vector<Line> st;
    LiChao(int n) : n(n), st(4 * n) {}

    inline void add(Line line, int v, int tl, int tr){
        if(st[v].m == INT32_MAX){
            st[v] = line;
            return;
        }
        int mid = (tl + tr) / 2;
        if(line.eval(mid) < st[v].eval(mid)){
            swap(line, st[v]);
        }
        if(tl == tr) return;

        if(line.m <= st[v].m){
            add(line, 2 * v + 1, mid + 1, tr);
        }
        else{
            add(line, 2 * v, tl, mid);
        }
        return;
    }

    inline void add(Line line){
        add(line, 0, 1, n);
    }

    inline int query(int x, int v, int tl, int tr){
        if(st[v].m == INT32_MAX) return LLONG_MAX;
        if(tl == tr) return st[v].eval(x);
        int mid = (tl + tr) / 2;
        if(x <= mid){
            return min(st[v].eval(x), query(x, 2 * v, tl, mid));
        }
        else{
            return min(st[v].eval(x), query(x, 2 * v + 1, mid + 1, tr));
        }
    }

    inline int query(int x){
        return query(x, 0, 1, n);
    }
};

inline void solve(){
    int n;
    cin >> n;
    vi h(n + 1), w(n + 1), pref(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> w[i];
        pref[i] = w[i] + pref[i - 1];
    }

    LiChao lc(MAXH);
    vi dp(n + 1);
    lc.add(Line(-2 * h[1], h[1] * h[1]));
    for(int i = 2; i <= n; i++){
        dp[i] = lc.query(h[i]) + h[i] * h[i] + pref[i - 1];
        lc.add(Line(-2 * h[i], dp[i] + h[i] * h[i] - pref[i]));
    }
    cout << dp[n] << "\n";
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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