Submission #1078726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078726		vjudge1	Building Bridges (CEOI17_building)	C++17	0 / 100	32 ms	36436 KiB

building

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct {
    struct line{
        int K;
        ll B;
        line(int k,ll b){
            K=k,B=b;
        }
        line(){
            K=0;
            B=1e18;
        }
        inline ll operator()(int x){
            return K*x+B;
        }
    } T[1<<21];
    void update(int i,int l,int r,line s){
        if(l==r-1){
            if(s(l)<T[i](l))
                swap(s,T[i]);
            return;
        }
        if(s.K<T[i].K)
            swap(s,T[i]);
        if(s(l+r>>1) < T[i](l+r>>1))
            swap(s,T[i]),update(i*2+1,l+r>>1,r,s);
        else update(i*2,l,l+r>>1,s);
    }
    ll query(int i,int l,int r,int p){
        if(T[i].B==1e18)
            return 1e18;
        if(l==r-1)
            return T[i](p);
        if(p<l+r>>1)
            return min(T[i](p),query(i*2,l,l+r>>1,p));
        else return min(T[i](p),query(i*2+1,l+r>>1,r,p));
    }
    void add_line(int k,ll b){
        update(1,0,1e6+1,line(k,b));
    }
    ll calc_best(int pos){
        return query(1,0,1e6+1,pos);
    }
} lichao;
ll h[100100],w[100100],dp[100100];
void update_dp(int i){
    lichao.add_line(-2*h[i],h[i]*h[i]-w[i]+dp[i]);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    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=2;i<=n;i++){
        update_dp(i-1);
        w[i]+=w[i-1];
        dp[i]=lichao.calc_best(h[i])+h[i]*h[i]+w[i-1];
    }
    cout<<dp[n]<<'\n';
}

Compilation message (stderr)

building.cpp: In member function 'void<unnamed struct>::update(int, int, int, <unnamed struct>::line)':
building.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         if(s(l+r>>1) < T[i](l+r>>1))
      |              ~^~
building.cpp:27:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         if(s(l+r>>1) < T[i](l+r>>1))
      |                             ~^~
building.cpp:28:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |             swap(s,T[i]),update(i*2+1,l+r>>1,r,s);
      |                                       ~^~
building.cpp:29:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         else update(i*2,l,l+r>>1,s);
      |                           ~^~
building.cpp: In member function 'll<unnamed struct>::query(int, int, int, int)':
building.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   36 |         if(p<l+r>>1)
      |              ~^~
building.cpp:37:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |             return min(T[i](p),query(i*2,l,l+r>>1,p));
      |                                            ~^~
building.cpp:38:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         else return min(T[i](p),query(i*2+1,l+r>>1,r,p));
      |                                             ~^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40