Submission #877166

#	Time	Username	Problem	Language	Result	Execution time	Memory
877166		votranngocvy	Building Bridges (CEOI17_building)	C++14	0 / 100	41 ms	4948 KiB

building

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

#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
const int N = 1e5 + 5;
const int MAX = 1e6;
const int inf = 0x3f3f3f3f3f3f3f3f;
pii st[4 * MAX + 5];
int h[N],w[N],n;

int f(pii a,int x) {
    return a.fi * x + a.se;
}

void update(int id,int l,int r,pii newLine) {
    int mid = (l + r) / 2;
    if (f(newLine,l) >= f(st[id],l) && f(newLine,r) >= f(st[id],r)) return;
    if (f(newLine,l) <= f(st[id],l) && f(newLine,r) <= f(st[id],r)) {
        st[id] = newLine;
        return;
    }
    if (f(st[id],l) <= f(newLine,l) && f(st[id],mid) <= f(newLine,mid)) {
        update(id * 2 + 1,mid + 1,r,newLine);
        return;
    }
    if (f(st[id],l) >= f(newLine,l) && f(st[id],mid) >= f(newLine,mid)) {
        update(id * 2 + 1,mid + 1,r,st[id]);
        st[id] = newLine;
        return;
    }
    if (f(st[id],r) <= f(newLine,r) && f(st[id],mid + 1) <= f(newLine,mid + 1)) {
        update(id * 2,l,mid,newLine);
        return;
    }
    if (f(st[id],r) >= f(newLine,r) && f(st[id],mid + 1) >= f(newLine,mid + 1)) {
        update(id * 2,l,mid,st[id]);
        st[id] = newLine;
        return;
    }
    update(id * 2,l,mid,newLine);
    update(id * 2 + 1,mid + 1,r,newLine);
}

int get(int id,int l,int r,int x) {
    if (r < x || l > x) return inf;
    int ans = f(st[id],x);
    if (l == r) return ans;
    int mid = (l + r) / 2;
    ans = min(ans,get(id * 2,l,mid,x));
    ans = min(ans,get(id * 2 + 1,mid + 1,r,x));
    return ans;
}

signed 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];
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    pii tmp = mp(-2 * h[1],h[1] * h[1] - w[1]);
    update(1,0,MAX,tmp);
    for (int i = 2; i < n; i++) {
        int val = get(1,0,MAX,h[i]) + h[i] * h[i] - w[i];
        tmp = mp(-2 * h[i],val + h[i] * h[i]);
        update(1,0,MAX,tmp);
    }
    cout << sum + get(1,0,MAX,h[n]) + h[n] * h[n] - w[n] << "\n";
}

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