제출 #1338171

#제출 시각아이디문제언어결과실행 시간메모리
1338171pobeBitaro the Brave 2 (JOI25_ho_t2)C++20
100 / 100
383 ms39580 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int v = - 2e9;
    int d = 0;
};
class segment_tree {
    int n;
    vector <node> tree;
    node merge(node a, node b) {
        node c;
        c.v = max(a.v, b.v);
        return c;
    }
    void apply(int num, int d) {
        tree[num].d += d;
        tree[num].v += d;
    }
    void push(int num) {
        if (tree[num].d) {
            apply(2 * num + 1, tree[num].d);
            apply(2 * num + 2, tree[num].d);
            tree[num].d = 0;
        }
    }
    void upt(int num, int l, int r, int low, int high, int v) {
        if (l >= low && r <= high) {
            apply(num, v);
            return;
        }
        push(num);
        int med = (l + r) / 2;
        if (med > low) {
            upt(2 * num + 1, l, med, low, high, v);
        }
        if (med < high) {
            upt(2 * num + 2, med, r, low, high, v);
        }
        tree[num] = merge(tree[2 * num + 1], tree[2 * num + 2]);
    }
    void build(int num, int l, int r, vector <int> &val) {
        if (l == r - 1) {
            tree[num].v = val[l];
            return;
        }
        int med = (l + r) / 2;
        build(2 * num + 1, l, med, val);
        build(2 * num + 2, med, r, val);
        tree[num] = merge(tree[2 * num + 1], tree[2 * num + 2]);
    }
public:
    void init(int nn, vector <int> &val) {
        n = nn;
        tree.resize(4 * n);
        build(0, 0, n, val);
    }
    int get() {
        return tree[0].v;
    }
    void upt(int l, int r, int v) {
        if (l >= r) {
            return;
        }
        upt(0, 0, n, l, r, v);
    }
};

void bad() {
    int n;
    cin >> n;
    vector <int> a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        sum += b[i];
    }
    segment_tree now;
    now.init(n, a);
    for (int i = 0; i < n - 1; ++i) {
        now.upt(i + 1, n, - b[i]);
    }
    int ans = 2e18;
    for (int i = 0; i < n; ++i) {
        ans = min(ans, now.get());
        now.upt(i + 1, n, b[i]);
        now.upt(0, i, b[i]);
        now.upt(i, i + 1, - (sum - b[i]));
    }
    cout << max(0LL, ans) << '\n';
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
//    cin >> t;
    for (int i = 0; i < t; ++i) {
        bad();
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...