Submission #1104764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104764		ardadut	Building Bridges (CEOI17_building)	C++17	0 / 100	30 ms	3152 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 = 1e18, c = 1e18;
    ll f(ll x){return m * x + c;}
};

ll n,total = 0;
const ll maxn = 1e5+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 = new_line.f(tl) < tree[node].f(tl);
    bool m = new_line.f(mid) < tree[node].f(mid);

    if(mid) swap(tree[node],new_line);
    if(tr - tl == 1) return;
    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 = tree[node].f(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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40