Submission #1337063

#TimeUsernameProblemLanguageResultExecution timeMemory
1337063biankBuilding Bridges (CEOI17_building)C++20
100 / 100
54 ms35604 KiB
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vb = vector<bool>;
using pll = pair<ll, ll>;
using i128 = __int128;

#define sz(x) int(x.size())
#define all(x) begin(x), end(x)

#define pb push_back
#define eb emplace_back

#define fst first
#define snd second

const ll INF = 1e18;

const int SZ = 1 << 20;

#define get(p, x) p.fst * x + p.snd

pll st[2 * SZ];

void update(pll l, int lo = 0, int hi = SZ, int u = 1) {
    if (hi - lo == 1) {
        if (get(l, lo) < get(st[u], lo)) swap(st[u], l);
        return;
    }
    int mid = (lo + hi) / 2;
    if (get(l, mid) < get(st[u], mid)) swap(st[u], l);
    if (get(st[u], lo) < get(l, lo)) {
        update(l, mid, hi, 2 * u + 1);
    } else {
        update(l, lo, mid, 2 * u);
    }
}

ll query(int x, int lo = 0, int hi = SZ, int u = 1) {
    if (hi - lo == 1) return get(st[u], x);
    int mid = (lo + hi) / 2;
    if (x < mid) return min(get(st[u], x), query(x, lo, mid, 2 * u));
    return min(get(st[u], x), query(x, mid, hi, 2 * u + 1));
}

int main() {
    ios::sync_with_stdio(0);                
    cin.tie(0); cout.tie(0);
    
    forn(i, 2 * SZ) st[i] = {0, INF};
    
    int n;
    cin >> n;
    vi h(n), w(n);
    forn(i, n) cin >> h[i];
    forn(i, n) cin >> w[i];
    
    vll pref(n + 1);
    forn(i, n) pref[i + 1] = pref[i] + w[i];
    
    vll dp(n);
    dp[0] = 0;
    
    forsn(i, 1, n) {
        pll l;
        l.fst = -2LL * h[i - 1];
        l.snd = 1LL * h[i - 1] * h[i - 1] - pref[i] + dp[i - 1];
        update(l);
        dp[i] = 1LL * h[i] * h[i] + pref[i] + query(h[i]);
    }
    cout << dp[n - 1] << "\n";
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...