319C - Kalila and Dimna in the Logging Industry - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

// Nome: Kalila and Dimna in the Logging Industry
// f(i) = f(j) + ai * bj
// b is decreasing
// a is increasing

typedef long long ll;

struct line{ll slope, y0;};

ll n, a[100010], b[100010];
deque <line> hull;

ll evaluate(line l, ll x){
    return l.slope * x + l.y0;
}

ll intersectionx(line a, line b){
    return (a.y0 - b.y0) / (b.slope - a.slope);
}

line query(ll x){
    while(hull.size() > 1){
        if(evaluate(hull[0], x) < evaluate(hull[1], x)) break;
        hull.pop_front();
    }
    return hull.front();
}

void update(line l){
    ll s = hull.size();
    while(s > 1){
        ll x1 = intersectionx(l, hull[s-1]);
        ll x2 = intersectionx(hull[s-2], hull[s-1]);
        if(x1 > x2) break;
        hull.pop_back();
        s--;
    }
    hull.push_back(l);
}

int main(){

    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for(ll i=0;i<n;i++) cin >> a[i];
    for(ll i=0;i<n;i++) cin >> b[i];

    ll f[n];
    f[0] = 0;

    hull.push_back({b[0], f[0]});
    for(ll i=1;i<n;i++){
        f[i] = evaluate(query(a[i]), a[i]);
        update({b[i], f[i]});
    }

    cout << f[n-1] << '\n';

    return 0;
}