oj.uz

Submission #349405

# Submission time Handle Problem Language Result Execution time Memory
349405 2021-01-17T14:29:52 Z doowey Building Bridges (CEOI17_building) C++14
30 / 100
 3000 ms 3480 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
const ld INF = (ld)4e18;
int h[N];
ll w[N];
ll dp[N];

ll sq(ll x){
    return (x * 1ll * x);
}

bool Q;

struct Line{
    ld ai;
    ld bi;
    mutable ld lim;
    // y = ax + b
    bool operator< (const Line &F) const {
        if(!Q){
            return ai < F.ai;
        }
        else{
            return lim < F.lim;
        }
    }
};

struct Hull : multiset<Line>{
    ld intersect(Line A, Line B){
        return (A.bi-B.bi)/(B.ai-A.ai);
    }
    bool check(iterator vv){
        auto pv = vv;
        auto nx = vv;
        if(pv == begin()) return true;
        nx ++ ;
        if(nx == end()) return true;
        if(intersect(*pv,*nx) <= intersect(*pv,*vv)){
            return false;
        }
        return true;
    }
    void upd(iterator &Q){
        auto nx = Q;
        nx ++ ;
        if(nx == end()){
            Q->lim = INF;
        }
        else{
            Q->lim=intersect(*Q, *nx);
        }
    }
    void ins(ld aa, ld bb){ // we construct lower hull
        aa=-aa;
        bb=-bb;
        Q = false;
        auto it = lower_bound({aa, bb, 0});
        if(it->ai == aa){
            if(bb <= it->bi){
                return;
            }
            else{
                erase(it);
            }
        }
        it = insert({aa,bb,0});
        if(!check(it)){
            erase(it);
            return;
        }
        auto pv = it;
        while(pv != begin()){
            pv--;
            if(check(pv)) break;
            pv=erase(pv);
        }
        pv = it;
        pv++;
        while(pv != end()){
            if(check(pv)) break;
            pv=erase(pv);
        }
        upd(it);
        if(it != begin()){
            it--;
            upd(it);
        }
    }
    ll get(ld X){
        Q=true;
        auto it = lower_bound({0,0,X});
        return -(X*1ll*(it->ai)+(it->bi));
    }

};

ll ax[N];
ll bx[N];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> h[i];
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> w[i];
        w[i] += w[i - 1];
        dp[i]=inf;
    }
    dp[1]=0;
    Hull dpv;
    for(int i = 1; i <= n; i ++ ){
        if(i > 1){
            for(int j = i - 1; j >= 1; j -- ){
                dp[i]=min(dp[i],ax[j]*1ll*h[i]+bx[j]+sq(h[i])+w[i-1]);
            }
            //dp[i]=dpv.get(h[i])+sq(h[i])+w[i-1];
        }
        ax[i]=-2ll*h[i];
        bx[i]=sq(h[i])-w[i]+dp[i];
        //dpv.ins(ax[i],bx[i]);
    }
    cout << dp[n];
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 3480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Execution timed out 3068 ms 3480 KB Time limit exceeded
7 Halted 0 ms 0 KB -