Submission #993411

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define N 2000100
int n, m;
ll a[N];
ll s[N];
ll f[N];

int main() {
	cin >> n;
	for (int i = 0; i < n-1; i ++) cin >> a[i];
	for (int i = 0; i < n-1; i ++) s[i+1] = s[i] + a[i];
	
	for (int i = 0; i <= s[2]; i++)
		f[i] = s[1]*2-i;
	
	for (int i = 3; i <= n-1; i ++) {
		for (int j = s[i-1]+1; j <= s[i]; j ++) {
			ll mi = 2*s[i-1]-j;
			if (mi < 0) f[j] = s[1]*2-mi;
			else f[j] = f[mi];
		}
	}
	cin >> m;
	while (m--) {
		int x; cin >> x;
		s[n] = s[n-1] + x;
		ll mi = 2*s[n-1] - s[n];
		if (mi < 0) cout << s[1]*2-mi << endl;
		else cout << f[mi]<< endl;
	}
	return 0;
}

Submission Info

Judge Result