제출 #467831

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467831		JovanB	Building Bridges (CEOI17_building)	C++17	100 / 100	93 ms	10460 KiB

building

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
struct line{
    ll k, n;
} seg[400005];
 
ll h[100005];
ll w[100005];
ll dp[100005];
ll niz[100005];
ll pos[10000005];
 
const int INF1 = 1e9;
const ll INF2 = 1e15;
 
void init(int node, int l, int r){
    seg[node] = {INF1, INF2};
    if(l == r) return;
    int mid = (l+r)/2;
    init(node*2, l, mid);
    init(node*2+1, mid+1, r);
}
 
ll eval(line a, ll b){
    return a.k*b + a.n;
}
 
ll getval(int node, int l, int r, int i){
    //cout << seg[node].k << " " << seg[node].n << " " << i << endl;
    ll tren = eval(seg[node], niz[i]);
    if(l == r) return tren;
    int mid = (l+r)/2;
    if(i <= mid) return min(tren, getval(node*2, l, mid, i));
    else return min(tren, getval(node*2+1, mid+1, r, i));
}
 
void addline(int node, int l, int r, line g){
    if(l == r){
        if(eval(g, niz[l]) <= eval(seg[node], niz[l])) seg[node] = g;
        return;
    }
    int mid = (l+r)/2;
    ll al = eval(g, niz[l]);
    ll bl = eval(seg[node], niz[l]);
    ll ar = eval(g, niz[r]);
    ll br = eval(seg[node], niz[r]);
    ll amid = eval(g, niz[mid]);
    ll bmid = eval(seg[node], niz[mid]);
    if(al <= bl && ar <= br){
        seg[node] = g;
        return;
    }
    if(al <= bl || amid <= bmid) addline(node*2, l, mid, g);
    if(ar <= br || amid <= bmid) addline(node*2+1, mid+1, r, g);
}
 
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    int n;
    cin >> n;
    vector <int> hs;
    for(int i=1; i<=n; i++){
        cin >> h[i];
        hs.push_back(h[i]);
    }
    int nn = 0;
    sort(hs.begin(), hs.end());
    for(auto c : hs){
        if(niz[nn] != c || nn == 0) niz[++nn] = c;
    }
    for(int i=1; i<=nn; i++) pos[niz[i]] = i;
    init(1, 1, nn);
    for(int i=1; i<=n; i++){
        cin >> w[i];
        w[i] += w[i-1];
        ll jos = w[i-1] + h[i]*h[i];
        dp[i] = jos+getval(1, 1, nn, pos[h[i]]);
        dp[1] = 0;
        //cout << i << " " << jos << " " << dp[i] << endl;
        line g;
        g.k = -2*h[i];
        g.n = -w[i] + h[i]*h[i] + dp[i];
        //cout << n << " "
        //cout << g.k << " " << g.n << endl;
        addline(1, 1, nn, g);
    }
    //for(int i=1; i<=n; i++) cout << dp[i] << " " << i << endl;
    cout << dp[n];
    return 0;
}

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