oj.uz

Submission #656393

# Submission time Handle Problem Language Result Execution time Memory
656393 2022-11-07T09:02:58 Z AkiYuu Building Bridges (CEOI17_building) C++17
0 / 100
 41 ms 9400 KB 
#include <bits/stdc++.h>
#define ll long long
#define ffw(i,a,b) for(int i = a; i<= b; i++)

using namespace std;
const int mxn= 1e5  +7;
const ll INF = 1e18;
struct line{
    ll A, B;
    ll operator()(const ll &x){
        return A*x + B;
    }
};

struct lichao{
    vector< line > tree;
    int  N;

    lichao(int _n ){
        N = _n;
        ffw(i,0,4*N + 6) tree.push_back({0,INF});
    }

    void add(line cur, ll x, int lx, int rx){
        if ( lx == rx ) {
            if ( cur(lx) < tree[x](lx) ) tree[x] = cur;
            return;
        }

        ll m = (lx + rx) / 2;
        if ( cur.A > tree[x].A  ) swap(tree[x] , cur);
        if ( cur(m) < tree[x](m) ) {
            swap(cur,tree[x]);
            add(cur, 2*x,lx,m);
        } else add(cur,2*x+1,m+1,rx);
    }

    void add(line cur){
        add(cur,1,1,N);
    }

    ll get(ll val, int x,int lx, int rx){
        if ( lx == rx) return tree[x](val);
        int m  = ( lx + rx)  /2;
        return min(tree[x](val), get(val, 2*x, lx,m) );
    }

    ll get(ll val){
        return get(val, 1,1,N);
    }
};

int n;
ll h[mxn];
ll s[mxn];
ll w[mxn];

void solve(){

    cin >> n;
    ffw(i,1,n) cin >> h[i];
    lichao bag(n + 1);

    cin >> w[1];
    s[1] = w[1];
    bag.add({2*h[1], h[1] * h[1] - s[1]});
    ffw(i,2,n){
        cin >> w[i];
        s[i] = s[i-1] + w[i];
        ll cur = bag.get(-h[i]) + h[i] * h[i] + s[i-1];
        bag.add({2*h[i], h[i] * h[i] + cur -  s[i]});
        if ( i == n )
            cout << cur << '\n';
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("xaycau.inp", "r", stdin);
//    freopen("xaycau.out", "w", stdout);

    solve();

}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 9400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -