Submission #994293

---

Source Code Expand

#include <algorithm>
#include <iostream>
using namespace std;

const int N = (int) 2e5 + 7;
int sum[N];
int a[N];
int f[N];

int main() {
    ios::sync_with_stdio(false);
    int n; cin >> n;
    for (int i = 0; i < n - 1; ++i) cin >> a[i];
    int m; cin >> m;
    for (int i = 0; i < n - 1; ++i) sum[i + 1] = sum[i] + a[i];
    for (int zzz = 0; zzz < m; ++zzz) {
        cin >> a[n - 1];
        sum[n] = sum[n - 1] + a[n - 1];
        f[n - 1] = -a[n - 1];
        int best = f[n - 1] + sum[n - 1];
        for (int i = n - 2; i > 0; --i) {
            f[i] = sum[i] - best;
            best = min(best, f[i] + sum[i]);
        }
        cout << f[1] + a[0] << endl;
    }
    return 0;
}

Submission Info

Judge Result