Submission #1177488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177488		YugiHacker	Building Bridges (CEOI17_building)	C++17	100 / 100	64 ms	66120 KiB

building

/*
	www.youtube.com/YugiHackerChannel
	linktr.ee/YugiHacker
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 100005
using namespace std;
struct Line {
    long long a, b;
    Line() {
        b = 1e18;
    }
    Line(long long a, long long b):a(a), b(b){};
    long long f(long long x) {
        return a*x+b;
    }
};
struct Segment {
    int n;
    vector <Line> t;
    Segment(){}
    Segment(int n):n(n) {
        t.resize(n*4+5);
    }
    void update(int id, int l, int r, Line _l) {
        if (l == r) {
            if (_l.f(l) < t[id].f(l)) t[id] = _l;
            return;
        }
        int mid = l + r >> 1;
        bool ok_m = _l.f(mid) < t[id].f(mid);
        bool ok_l = _l.f(l) < t[id].f(l);
        if (ok_m) swap(t[id], _l);
        if (ok_l == ok_m) update(id*2+1, mid+1, r, _l);
        else update(id*2, l, mid, _l);
    }
    long long get(int id, int l, int r, int pos) {
        if (l == r) return t[id].f(l);
        int mid = (l + r) / 2;
        if (pos <= mid) return min(t[id].f(pos), get(id*2, l, mid, pos));
        return min(t[id].f(pos), get(id*2+1, mid+1, r, pos));
    }
};
int n;
long long h[maxn], w[maxn], s[maxn], dp[maxn];
/*
    dp[i] = min(dp[j] + (h[i] - h[j]) ^ 2 + s[i-1] - s[j])
    dp[i] = -2h[j] * h[i] + h[j] * h[j] + dp[j] - s[j]
            + s[i] - w[i] + h[i] ^ 2
*/
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++) cin >> h[i];
    for (int i=1; i<=n; i++) cin >> w[i], s[i] = s[i-1] + w[i];
    int maxh = 1e6;
    Segment seg(maxh);
    dp[1] = 0;
    seg.update(1, 0, maxh, Line(-2 * h[1], h[1] * h[1] + dp[1] - s[1]));
    for (int i=2; i<=n; i++) {
        dp[i] = seg.get(1, 0, maxh, h[i]) + s[i] - w[i] + h[i] * h[i];
        seg.update(1, 0, maxh, Line(-2 * h[i], h[i] * h[i] + dp[i] - s[i]));
    }
    cout << dp[n];
}

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