Submission #1078749

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

building

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
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(T[i].B==1e18) return void(T[i]=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]);
        int mid=l+r>>1;
        if(s(mid) < T[i](mid))
            swap(s,T[i]),update(i*2+1,mid,r,s);
        else update(i*2,l,mid,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,-1,1e6+1,line(k,b));
    }
    ll calc_best(int pos){
        return query(1,-1,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]);
}
signed 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(long long int, long long int, long long int, <unnamed struct>::line)':
building.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |         int mid=l+r>>1;
      |                 ~^~
building.cpp: In member function 'll<unnamed struct>::query(long long int, long long int, long long int, long long int)':
building.cpp:39:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         if(p<l+r>>1)
      |              ~^~
building.cpp:40:45: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |             return min(T[i](p),query(i*2,l,l+r>>1,p));
      |                                            ~^~
building.cpp:41:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         else return min(T[i](p),query(i*2+1,l+r>>1,r,p));
      |                                             ~^~

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