Submission #1182767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182767		btninh	Building Bridges (CEOI17_building)	C++20	100 / 100	41 ms	18408 KiB

building

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

#define btninh signed main
#define int long long
#define REP(i, n) for(int i = 0; i < n; ++i)
#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 fast ios::sync_with_stdio(0); cin.tie(0)
#define IO(x) if(fopen(x".inp","r")){freopen(x".inp","r",stdin);freopen(x".out","w",stdout);}
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first
#define se second
#define pb push_back
#define pii pair<int,int>
template<class Typ> bool mini(Typ &x, Typ y){if (x > y) return x = y, true; return false;}
template<class Typ> bool maxi(Typ &x, Typ y){if (x < y) return x = y, true; return false;}
const int N = 100003;
const int inf = 1e18;

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

struct Line{
    int a, b;
    Line (int a, int b): a(a), b(b) {};
    int slope(){return a;}
    int calc(int x){
        return a * x + b;
    }
};

namespace lichao{
    vector<Line> it;

    void init(){
        it.resize(1000003, Line(0, inf));
    }

    void upd(Line f, int l, int r){
        if (l > r) return;
        if (l == r){
            if (f.calc(l) < it[l].calc(l)) it[l] = f;
            return;
        }
        int mid = (l + r) / 2;
        if (f.calc(mid) < it[mid].calc(mid)) swap(f, it[mid]);
        if (f.slope() > it[mid].slope()) upd(f, l, mid - 1);
        if (f.slope() < it[mid].slope()) upd(f, mid + 1, r);
    }

    int get(int pos, int l, int r){
        int mid = (l + r) / 2;
        int cur = it[mid].calc(pos);
        if (pos == mid) return cur;
        if (pos < mid) return min(cur, get(pos, l, mid - 1));
        return min(cur, get(pos, mid + 1, r));
    }
};

btninh(){
    fast;
    //IO("main");

    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) {
        cin >> w[i];
        pre[i] = pre[i - 1] + w[i];
    }
    lichao::init();
    lichao::upd(Line(-2 * h[1], h[1] * h[1] - pre[1]), 0, 1e6);
    int cur;
    FOR(i, 2, n){
        cur = lichao::get(h[i], 0, 1e6) + h[i] * h[i] + pre[i - 1];
        lichao::upd(Line(-2 * h[i], cur + h[i] * h[i] - pre[i]), 0, 1e6);
    }
    cout << cur;
}

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