oj.uz

Submission #1104647

# Submission time Handle Problem Language Result Execution time Memory
1104647 2024-10-24T08:06:43 Z ardadut Building Bridges (CEOI17_building) C++17
0 / 100
 20 ms 9040 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 void pre(){
    for(ll i = 1 ; i <= maxn * 4 ; i++){
        tree[i].first = 0;
        tree[i].second = 1e18;
    }
}

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];

    pre();

    dp[1] = -w[1];

    for(ll i = 2 ; i <= n ; i++){
        add(1,maxn,{-2 * h[i-1], dp[i-1] + h[i-1] * h[i-1]},1);
        dp[i] = query(1,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();
    }
    
}

Compilation message

building.cpp: In function 'void pre()':
building.cpp:28:23: warning: iteration 400019 invokes undefined behavior [-Waggressive-loop-optimizations]
   28 |         tree[i].first = 0;
      |         ~~~~~~~~~~~~~~^~~
building.cpp:27:22: note: within this loop
   27 |     for(ll i = 1 ; i <= maxn * 4 ; i++){
      |                    ~~^~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 40.0

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