Submission #1104796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104796		ardadut	Building Bridges (CEOI17_building)	C++17	100 / 100	51 ms	10068 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*/

struct Line{
    ll m = 0, c = 1e18;
};

inline ll f(Line line, ll x){
    return line.m * x + line.c;
}

ll n,total = 0;
const ll maxn = 1e6+5;
ll h[maxn];
ll w[maxn];
ll dp[maxn];
Line tree[4*maxn];

inline void add(ll tl, ll tr, Line new_line, ll node){

    ll mid = (tl + tr) / 2;
    bool l = f(new_line,tl) < f(tree[node],tl);
    bool m = f(new_line,mid) < f(tree[node],mid);
    
    if(m) swap(tree[node],new_line);

    if(tr - tl == 1) return;
    else if(l != m) add(tl,mid,new_line,node*2+1);
    else add(mid,tr,new_line,node*2+2);
}

inline ll query(ll tl, ll tr, ll node, ll x){

    ll mid = (tl + tr) / 2;
    ll ans = f(tree[node],x);

    if(tr - tl == 1) return ans;
    if(x < mid) return min(ans,query(tl,mid,node*2+1,x));
    else return min(ans,query(mid,tr,node*2+2,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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40