oj.uz

Submission #1078747

# Submission time Handle Problem Language Result Execution time Memory
1078747 2024-08-28T05:42:03 Z vjudge1 Building Bridges (CEOI17_building) C++17
0 / 100
 31 ms 35412 KB 
#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(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]);
}
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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33116 KB Output is correct
2 Incorrect 14 ms 33116 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 35412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 33116 KB Output is correct
2 Incorrect 14 ms 33116 KB Output isn't correct
3 Halted 0 ms 0 KB -