Submission #994099

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int N,M;
ll A[200005];
ll dp[200005][2][2];
const ll INF = 10000000000000000LL;
ll solve(int id,int pl,int fr){
  if( dp[id][pl][fr] != -1 ) return dp[id][pl][fr];
  if( id == N ) return dp[id][pl][fr] = 0;
  ll ret = 0;
  if( pl ) ret = -INF; //1:snuke
  else ret = INF; //0:rng

  if( fr ){//front
    ll st = solve(id+1,1-pl,0);
    if( pl ) ret = max( ret, st + A[id+1] );
    else ret = min( ret, st - A[id+1] );

    if( id < N-1 ) {    
      st = solve(id+1,pl,1);
      if( pl ) ret = max( ret, st - A[id+1] );
      else ret = min( ret, st + A[id+1] );
    }
  } else { //usual
    ll st = solve(id+1,1-pl,0);
    if( pl ) ret = max( ret, st ) + A[id+1];
    else ret = min( ret, st ) - A[id+1];

    if( id < N-1 ){
      st = solve(id+1,pl,1);
      if( pl ) ret = max( ret, st - A[id+1] );
      else ret = min( ret, st + A[id+1] );
    }
  }

  // cout << id << " " << pl << " "<< fr << " = " << ret << endl;
  return dp[id][pl][fr] = ret;
}

int main(){
  cin >> N;
  for(int i=0;i<N-1;i++)
    cin >> A[i];
  cin >> M;
  if( M > 2 ) return 0;
  for(int i=0;i<M;i++){
    int x; cin >> x;
    A[N] = x;
    memset( dp,-1,sizeof( dp ) ) ;
    cout << solve( 1, 1, 0 ) + A[0]-A[1]  << endl;
  }
}

Submission Info

Judge Result