oj.uz

Submission #35494

# Submission time Handle Problem Language Result Execution time Memory
35494 2017-11-23T01:14:42 Z imaxblue Building Bridges (CEOI17_building) C++14
100 / 100
 1253 ms 16908 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 506 ms 4500 KB Output is correct
2 Correct 503 ms 4500 KB Output is correct
3 Correct 509 ms 4500 KB Output is correct
4 Correct 436 ms 4368 KB Output is correct
5 Correct 563 ms 6876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4368 KB Output is correct
2 Correct 0 ms 4368 KB Output is correct
3 Correct 0 ms 4368 KB Output is correct
4 Correct 0 ms 4368 KB Output is correct
5 Correct 0 ms 4368 KB Output is correct
6 Correct 506 ms 4500 KB Output is correct
7 Correct 503 ms 4500 KB Output is correct
8 Correct 509 ms 4500 KB Output is correct
9 Correct 436 ms 4368 KB Output is correct
10 Correct 563 ms 6876 KB Output is correct
11 Correct 419 ms 4368 KB Output is correct
12 Correct 523 ms 4500 KB Output is correct
13 Correct 236 ms 4368 KB Output is correct
14 Correct 519 ms 4500 KB Output is correct
15 Correct 1253 ms 16908 KB Output is correct
16 Correct 569 ms 6876 KB Output is correct
17 Correct 96 ms 4368 KB Output is correct
18 Correct 79 ms 4368 KB Output is correct