Submission #1104672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104672		ardadut	Building Bridges (CEOI17_building)	C++17	0 / 100	22 ms	4688 KiB

building

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/
    
ll n,total = 0;
const ll maxn = 1e5+5;
ll h[maxn];
ll w[maxn];
ll dp[maxn];
pair<ll,ll> tree[4*maxn];
    
inline ll f(pair<ll,ll> func, ll x){
    return func.first * x + func.second;
}
    
inline void add(ll tl, ll tr, pair<ll,ll> new_func, ll node){
    ll mid = (tl+tr) / 2;
    bool l = f(new_func,tl) < f(tree[node],tl);
    bool m = f(new_func,mid) < f(tree[node],mid);
    
    if(m) swap(tree[node],new_func);
    if(tr - tl == 1) return;
    if(l != mid) add(tl,mid,new_func,node*2);
    else add(mid,tr,new_func,node*2+1); 
}
    
inline ll query(ll tl, ll tr, ll node, ll x){
    ll mid = (tl+tr) / 2;
    if(tr - tl == 1) return f(tree[node],x);
    
    if(x < mid) return min(f(tree[node],x),query(tl,mid,node*2,x));
    return min(f(tree[node],x),query(mid,tr,node*2+1,x));
}
    
inline void solve(){
    
    cin >> n;
    
    for(ll i = 1 ; i <= n ; i++) cin >> h[i];
    for(ll i = 1 ; i <= n ; i++) cin >> w[i], total += w[i];
    
    
    dp[1] = -w[1];
    
    for(ll i = 2 ; i <= n ; i++){
        add(0,maxn,{-2 * h[i-1], dp[i-1] + h[i-1] * h[i-1]},1);
        dp[i] = query(0,maxn,1,h[i]) - w[i] + h[i] * h[i];
    }
    
    cout << total + dp[n] << endl;
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

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