Submission #1325304

#TimeUsernameProblemLanguageResultExecution timeMemory
1325304ankithello20Building Bridges (CEOI17_building)C++20
100 / 100
60 ms10388 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct Line{
    bool type;
    double x;
    ll m,c; 
};

set<Line>cht;
bool operator<(Line l1,Line l2){
    if(l1.type || l2.type) return l1.x<l2.x;
    return l1.m>l2.m;
}

bool has_prev(set<Line>:: iterator it){
    return it !=cht.begin();
}
bool has_next(set<Line>::iterator it){
    if(it==cht.end()) return false;
    return next(it)!=cht.end();
}

double intersect(set<Line>::iterator l1,set<Line>::iterator l2){
    return (double)(l1->c-l2->c)/(l2->m-l1->m);
}

void calc_x(set<Line>::iterator it){
    if(has_prev(it)){
        Line newl=*it;
        newl.x= intersect(prev(it),it);
        cht.insert(cht.erase(it),newl);
    }
}

bool bad(set<Line>::iterator it){
    
    if(has_next(it) and next(it)->c<=it->c) return true;
    return (has_prev(it) and has_next(it) and intersect(prev(it),next(it))<=intersect(prev(it),it));
}

void add_line(long long m,long long c){
       set<Line>::iterator it;

       it=cht.lower_bound({0,0,m,c});

       if(it!=cht.end() and it->m==m){
             if(it->c<=c) return;
             cht.erase(it);
       }

       it=cht.insert({0,0,m,c}).first; // return iterator and second is boolean whether inserted or not
       


       if(bad(it)) {
           cht.erase(it);
       }
       else{
           while(has_prev(it) and bad(prev(it))) cht.erase(prev(it));
           while(has_next(it) and bad(next(it))) cht.erase(next(it));

           if(has_next(it)) calc_x(next(it));
           calc_x(it);
       }
       
       
}
long long query(ll h){
    
    Line l=*prev(cht.upper_bound({1,(double)h,0,0}));
    return l.m*h +l.c;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin>>n;
    vector<long long>h(n),w(n);

    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    long long total=0;

    for(int i=0;i<n;i++){
        cin>>w[i];
        total+=w[i];
    }



    vector<long long>dp(n);
    dp[0]=-w[0];
     add_line(-2*h[0],dp[0]+h[0]*h[0]);

    for(int i=1;i<n;i++){
        dp[i]=(query(h[i]) + 1ll*h[i]*h[i] -w[i]);
        add_line(-2*h[i],dp[i]+h[i]*h[i]);

    }

    cout<<total+dp[n-1]<<endl;



    

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...