Submission #35494

#	Time	Username	Problem	Language	Result	Execution time	Memory
35494		imaxblue	Building Bridges (CEOI17_building)	C++14	100 / 100	1253 ms	16908 KiB

building

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define p_q priority_queue
#define MN 1000000009

bool convex(pll X, pll O, pll Y){
    return (X.y-O.y+X.x*X.x-O.x*O.x)*(O.x-Y.x)
    <(O.y-Y.y+O.x*O.x-Y.x*Y.x)*(X.x-O.x);
}
set<pll> s[2];
ll n, w[100005], h[100005];
ll dp[100005], ans;
set<pll>::iterator x, y, z;
bool check1(int T, pll X){
        z=s[T].lb(X);
        if (z==s[T].begin() || z==s[T].end()) return 1;
        y=z; --y;
        if (y==s[T].begin()) return 1;
        x=y; --x;
        if (convex(*x, *y, *z)) return 1;
        s[T].erase(y);
        return 0;
}
bool check2(int T, pll X){
        y=s[T].lb(X);
        if (y==s[T].begin() || y==s[T].end()) return 1;
        z=y; ++z;
        if (z==s[T].end()) return 1;
        x=y; --x;
        if (convex(*x, *y, *z)) return 1;
        s[T].erase(y);
        return 0;
}
bool check3(int T, pll X){
		x=s[T].lb(X);
        if (x==s[T].end()) return 1;
        y=x; ++y;
        if (y==s[T].end()) return 1;
        z=y; ++z;
        if (z==s[T].end()) return 1;
        if (convex(*x, *y, *z)) return 1;
        s[T].erase(y);
        return 0;
}
void add(int T, pll X){
    y=s[T].ub(X);
    if (y==s[T].begin() || y==s[T].end());
    else {
        x=y; --x;
        if (!convex(*x, X, *y)) return;
    }
    s[T].insert(X);
    int f=3;
    while(f){
        f=3;
        f-=check1(T, X)+check2(T, X)+check3(T, X);
    }
}
ll sum(int T, ll H){
    int lo, mid, hi;
    ll t2;
    if (T==0) t2=1; else t2=-1;
    t2=1;
    if (T) {lo=-1000000; hi=H;}
    else {lo=0; hi=H;}
    //cout << "*" << s[T].size() << ' ' << hi << ' ';
    while(lo<hi){
        mid=(lo+hi+1)/2;
        y=s[T].lb(mp(mid, -(1LL << 60)));
        //cout << mid << ' ';
        if (y==s[T].begin()) lo=mid;
        else if (y==s[T].end() || y->x>H) hi=mid-1;
        else {
            x=y; --x;
            if (((H-x->x)*(H-x->x)+t2*x->y<(H-y->x)*(H-y->x)+t2*y->y)) hi=mid-1;
            else lo=mid;
        }
    }
    y=s[T].lb(mp(lo, -(1LL << 60)));
    if (y==s[T].end()) return (1LL << 60);
    ll ret=(H-y->x)*(H-y->x)+t2*y->y;
    /*int k;
    for (int l=0; l<50; ++l){
        k=rand()%1000000;
        if (T==2) k=-k;
        y=s[T].lb(mp(k, -(1LL << 60)));
        if (y==s[T].end()) continue;
        ret=min(ret, (H-y->x)*(H-y->x)+t2*y->y);
    }*/
    return ret;
}
int main() {
    srand(time(NULL));
    cin >> n;
    for (int l=0; l<n; ++l) cin >> h[l];
    for (int l=0; l<n; ++l){
        cin >> w[l]; ans+=w[l];
    }
    for (int l=0; l<n; ++l){
        if (l==0){
            dp[l]=-w[l];
        } else {
            dp[l]=(1LL << 60);
            dp[l]=min(sum(0, h[l]), sum(1, -h[l]))-w[l];
            //int C=0;
            //for (auto i:s[0]){
            //    dp[l]=min(i.y-w[l]+(i.x-h[l])*(i.x-h[l]), dp[l]);
            //}
        }
        //cout << dp[l] << endl;
        add(0, mp(h[l], dp[l]));
        add(1, mp(-h[l], dp[l]));
    }
    cout << ans+dp[n-1];
    return 0;
}

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