Submission #1347407

#TimeUsernameProblemLanguageResultExecution timeMemory
1347407abcd123456Building Bridges (CEOI17_building)C++20
100 / 100
55 ms66168 KiB
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define maxn 1000005
#define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define ll long long

using namespace std;

template<class T>
inline void read(T &x){
    x=0; char c=getchar(); bool f=0;
    for(;!isdigit(c);c=getchar()) f^=c=='-';
    for(;isdigit(c);c=getchar()) x=x*10+(c^48);
    x=f?-x:x;
}

template<class T>
inline void write(T x){
    if(x<0){ putchar('-'); x=-x; }
    T y=1; int len=1;
    for(;y<=x/10;y*=10) len++;
    for(;len;len--,x%=y,y/=10) putchar(x/y+48);
}

const int mod=1e9+7;
const int INF=4e18;
const int MAX=1e6;

struct Line {
   int a,b;
   Line(int _a=0,int _b=INF) : a(_a),b(_b) {}
   int get(int x) const {
      return a*x+b;
   }
};


struct Lichao {
   int n;
   vector<Line> st;
   Lichao(int _n=0){
     n=_n;
     st.assign(4*n+5,Line());
   }
   void add(int id,int l,int r,Line val){
      if(l==r){
        st[id]=(val.get(l) < st[id].get(l) ? val : st[id]);
        return ;
      }
      int m=(l+r)/2;
      if(val.get(m) < st[id].get(m)) swap(st[id],val);
      if(val.get(l) < st[id].get(l)) add(id*2,l,m,val);
      if(val.get(r) < st[id].get(r)) add(id*2+1,m+1,r,val);
   }
   int query(int id,int l,int r,int pos){
      ll cur=st[id].get(pos);
      int m=(l+r)/2;
      if(l==r) return cur;
      if(pos<=m) return min(cur,query(id*2,l,m,pos));
      else return min(cur,query(id*2+1,m+1,r,pos));
   }
};

int dp[maxn],pre[maxn];
int h[maxn],w[maxn],n;

signed main() {
    itachi
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i];
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<=n;i++){
        pre[i]=pre[i-1]+w[i];
    }
    Lichao tree(MAX+5);
    dp[1]=0;
    tree.add(1,0,MAX,Line(-2*h[1],dp[1]+h[1]*h[1]-pre[1]));
    for(int i=2;i<=n;i++){
        int best=tree.query(1,0,MAX,h[i]);
        dp[i]=h[i]*h[i]+pre[i-1]+best;
        tree.add(1,0,MAX,Line(-2*h[i],dp[i]+h[i]*h[i]-pre[i]));
    }
    cout<<dp[n];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...