oj.uz

Submission #1104672

# Submission time Handle Problem Language Result Execution time Memory
1104672 2024-10-24T08:33:30 Z ardadut Building Bridges (CEOI17_building) C++17
0 / 100
 22 ms 4688 KB 
#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.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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