oj.uz

Submission #1104796

# Submission time Handle Problem Language Result Execution time Memory
1104796 2024-10-24T12:34:21 Z ardadut Building Bridges (CEOI17_building) C++17
100 / 100
 51 ms 10068 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*/

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5708 KB Output is correct
2 Correct 34 ms 6728 KB Output is correct
3 Correct 32 ms 6736 KB Output is correct
4 Correct 29 ms 6472 KB Output is correct
5 Correct 29 ms 9544 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 2 ms 4432 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 32 ms 5708 KB Output is correct
7 Correct 34 ms 6728 KB Output is correct
8 Correct 32 ms 6736 KB Output is correct
9 Correct 29 ms 6472 KB Output is correct
10 Correct 29 ms 9544 KB Output is correct
11 Correct 51 ms 10068 KB Output is correct
12 Correct 47 ms 9800 KB Output is correct
13 Correct 33 ms 7752 KB Output is correct
14 Correct 41 ms 10056 KB Output is correct
15 Correct 29 ms 9544 KB Output is correct
16 Correct 32 ms 9544 KB Output is correct
17 Correct 22 ms 6472 KB Output is correct
18 Correct 23 ms 6472 KB Output is correct