Submission #1275877

---

Source Code Expand

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

using ll = long long;

int main() {
    int N;
    cin >> N;
    vector<ll> A(N+2), B(N+2);
    vector<ll> maB(N+2);
    for(int i=1; i<=N; ++i) {
        cin >> A[i];
    }
    for(int i=1; i<=N; ++i) {
        cin >> B[i];
        maB[i] = max(B[i], maB[i-1]);
    }
    ll ma = 0;
    vector<ll> v(N+2), u(N+2);
    for(int i=1; i<=N+1; ++i) {
        if(i != 1) {
            if(v[i-1] + A[i-1] >= 0) {
                v[i] = v[i-1] + 1;
                u[i] = u[i-1] + A[i-1];
            } else if(maB[i-1] == 0) {
                break;
            } else {
                ll minus = -(u[i-1] + A[i-1]);
                ll d = (minus + maB[i-1]-1) / maB[i-1];

                v[i] = v[i-1] + 1 + d;
                u[i] = u[i-1] + A[i-1] + d * maB[i-1];
            }
        }

        if(v[i] <= N) {
            ma = max(ma, u[i] + (N - v[i]) * maB[i]);
        }
    }
    cout << ma << endl;
}

Submission Info

Judge Result