Блекджек (Розбір)

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <bitset>
#include <map>
#include <vector>
#include <set>
#include <algorithm>

#define endl '\n'

using namespace std;

FILE* stream;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ld, ld > pdd;
const long long DIM = 500007;
const ld eps = 1e-12;
const long long INF = 1e18;
const long long Bsize = 450;
const int mod = 998244353;
const long long NUMSZ = 500;

struct line {
    ll k, b;

    line() {
        k = 0;
        b = 0;
    }

    line(ll k_, ll b_) {
        k = k_;
        b = b_;
    }

    ll get(ll x) {
        return (ll)k * (ll)x + (ll)b;
    }
};

ll intersection(const line& l1, const line& l2) {
    ll a = l2.b - l1.b;
    ll b = l1.k - l2.k;

    return a / b - ((a ^ b) < 0 && a % b);
}


class convexHull {
public:

    void init(int sz) {
        d.clear();
        d.resize(2 * sz + 5);
        L = sz;
        R = sz;
    }
    void add(line l) {
        if (R - L > 0 && d[R - 1].k == l.k) {
            if (d[R - 1].b >= l.b) return;
            R--;
        }

        while (R - L > 1 &&
            intersection(d[R - 2], d[R - 1]) >= intersection(d[R - 2], l)) {
            R--;
        }
        d[R++] = l;
    }


    ll query(ll x) {
        if (R - L == 0) return -INF;
        while (R - L > 1 && intersection(d[L], d[L + 1]) <= x) {
            L++;
        }
        return d[L].get(x);
    }

    void clear() {
        d.clear();
    }

private:

    int L, R;
    vector < line > d;
};

ll res[DIM];

class convexHullTree {
public:

    void init(int sz_) {
        sz = sz_;
        T.resize(4 * sz + 7);
    }

    void addLine(int L, int R, line l) {
        addLine(0, 1, sz, L, R, l);
    }

    void addQuery(int pos, ll x) {
        addQuery(0, 1, sz, pos, x);
    }

    void proces() {
        convexHull c;
        for (auto ver : T) {
            c.init(2 * ver.l.size());
            for (auto l : ver.l) c.add(l);
            for (auto x : ver.x) {
                res[x] = max(res[x], c.query(x));
            }
            c.clear();
        }
    }

private:

    void addLine(int v, int tl, int tr, int L, int R, line l) {
        if (L <= tl && tr <= R) {
            T[v].l.push_back(l);
            return;
        }
        if (tl > R || tr < L) return;

        int tm = (tl + tr) >> 1;

        addLine(2 * v + 1, tl, tm, L, R, l);
        addLine(2 * v + 2, tm + 1, tr, L, R, l);
    }

    void addQuery(int v, int tl, int tr, int pos, ll x) {
        T[v].x.push_back(x);
        if (tl == tr) {
            return;
        }

        int tm = (tl + tr) >> 1;
        if (pos <= tm) {
            addQuery(2 * v + 1, tl, tm, pos, x);
        }
        else {
            addQuery(2 * v + 2, tm + 1, tr, pos, x);
        }
    }

    struct node {
        vector < line > l;
        vector < ll > x;
    };

    int sz;
    vector < node > T;
};

struct queryLine {
    line l;
    ll L, R;
};

bool cmp(queryLine l1, queryLine l2) {
    return l1.l.k < l2.l.k;
}

vector < queryLine > Lq;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef _DEBUG
    freopen_s(&stream, "input.txt", "r", stdin);
    freopen_s(&stream, "output.txt", "w", stdout);
#endif

    int n;
    cin >> n;

    vector < ll > a(n + 1), k(n + 1), x(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> k[i];
    for (int i = 1; i <= n; i++) cin >> x[i];

    vector < ll > p = a;
    for (int i = 1; i <= n; i++) {
        p[i] += p[i - 1];
        if (k[i] == 0) {
            k[i] = 1;
            x[i] = 0;
        }
    }

    ll ans = -1e18;
    ll mxExp = -INF;

    vector < ll > events(n + 1, -INF);

    for (int i = 1; i <= n; i++) {
        if(i + k[i] - 1 <= n) events[i + k[i] - 1] = max(events[i + k[i] - 1], -p[i - 1] + k[i] * x[i]);
        Lq.push_back({ {x[i], -(ll)(i - 1) * x[i] - p[i - 1]}, i, i + k[i] - 1 });

        mxExp = max(mxExp, events[i]);

        ans = max(ans, mxExp + p[i]);
    }

    convexHullTree t;
    t.init(n);

    sort(Lq.begin(), Lq.end(), cmp);

    for (auto x : Lq) {
        if (x.L > x.R) continue;
        t.addLine(x.L, x.R, x.l);
    }
    for (int i = 1; i <= n; i++) {
        t.addQuery(i, i);
    }

    for (int i = 1; i <= n; i++) res[i] = -INF;
    t.proces();

    for (int i = 1; i <= n; i++) {
        ans = max(ans, p[i] + res[i]);
    }

    cout << ans << endl;

    return 0;
}