Submission #870863

#	Time	Username	Problem	Language	Result	Execution time	Memory
870863		dmmaythangflex21	Building Bridges (CEOI17_building)	C++17	0 / 100	22 ms	10520 KiB

building

#include<bits/stdc++.h>
using namespace std;
#define el cout << "\n";
#define ll long long
#define int ll
#define lb long double
#define pii pair<int, int>
#define All(a) a.begin(), a.end()
#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 FILE freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

pii H[] = {{-1, 0}, {0, -1}};
const int Mod = 1e9 + 7, inf = 1e18;
template<class A, class B> bool maximize(A &a, B b) { return a < b && (a = b, true); }
template<class A, class B> bool minimize(A &a, B b) { return a > b && (a = b, true); }
template<class A, class B> void add(A &a, B b) { a += b; if (a >= Mod) a -= Mod; }
template<class A, class B> void sub(A &a, B b) { a -= b; if (a < 0) a += Mod; }

#define maxn 1000100
int n, a[maxn], h[maxn], w[maxn], s[maxn], f[maxn];

struct Line{
    int a, b;
    Line(int a, int b){
        this -> a = a, this -> b = b;
    }
    Line(){}
    ll operator()(ll x){
        return a * x + b;
    }
};

struct LICHAO{
    int n; vector<Line> f;
    LICHAO(int n){
        this -> n = n; f.resize(4 * n + 1);
    }

    void add(int id, int l, int r, Line cur){
        if (l == r){
            if (cur(l) <= f[id](l)) f[id] = cur;
            return;
        }

        int mid = (l + r) >> 1;
        if (cur.a > f[id].a) swap(f[id], cur);
        if (f[id](mid) > cur(mid)){
            swap(f[id], cur);
            add(id * 2 + 1, mid + 1, r, cur);
        }

        else add(id * 2, l, mid, cur);
    } void add(Line cur){ add(1, 1, n, cur); }

    ll get(int id, int l, int r, ll x){
        ll ans = f[id](x);
        if (l == r) return ans;
        int mid = (l + r) >> 1;
        if (x >= mid) return min(ans, get(id * 2, l, mid, x));
        return min(ans, get(id * 2 + 1, mid + 1, r, x));
    } ll get(ll x){ return get(1, 1, n, x); }
};

LICHAO t(maxn);
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    #define name "enn"
//    FILE
    cin >> n;
    FOR(i, 1, n) cin >> h[i];
    FOR(i, 1, n) cin >> w[i], s[i] = s[i - 1] + w[i];

    f[1] = 0;
    t.add(Line(-2 * h[1], h[1] * h[1]));
    FOR(i, 2, n){
        f[i] = t.get(h[i]) + h[i] * h[i] + s[i - 1];
        t.add(Line(-2 * h[i], f[i] - s[i] + h[i] * h[i]));
    }

    cout << f[n];

}

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