Submission #1005589

---

Source Code Expand

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

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

int N;
const int MAXN = 200002;
int A[MAXN];
ll dp[MAXN], sum[MAXN], memo[MAXN];

int main() {
	cin >> N;
	for (int i = 0; i < N-1; i++)
		cin >> A[i];
	int Q;
	cin >> Q;
	int X;
	cin >> X;
	A[N-1] = X;
	for (int i = 0; i < N; i++)
		sum[i+1] = sum[i] + A[i];
	memo[N-1] = A[N-1] - sum[N-1];
	ll maxi = memo[N-1];
	memo[N] = -1ll<<60;
	for (int i = N-2; i >= 0; i--) {
		maxi = max(maxi, memo[i+2]);
		dp[i] = maxi + sum[i+2];
		memo[i+1] = A[i+1] - sum[i+1] - dp[i];
	}
	cout << dp[0] + A[0] - A[1] << endl;
	return 0;
}

Submission Info

Judge Result