IOICJ 109 Big Tower ( DP, Deque )

Problem Description:
There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to travel to the N'th floor, abiding by these rules:
1. From the starting room of each floor, you are to choose either left or right, and you may only move to that direction during your travel on that floor.
2. Every room has a path towards the room with the same number, and one floor higher than the current floor.
3. At every floor, except the starting point, you may only travel at most A number of rooms, each room at most once, and not to skip any room.
You want to know the maximum total score you may receive.

Constraints:
1≤T≤15
1≤N≤15
1≤M≤1e5
1≤X≤M
1≤A≤M
−500≤Sij≤500
TL: 6000 ms

Sample Input:
3
3 3 2 1
7 8 1
4 5 6
1 2 3
2 2 1 1
5 -1
5 3
4 3 2 1
4 2 0
-2 5 5
4 -4 1
0 4 5

Sample Output:
29
13
22

Solution:
We would traverse over each floor from the bottom to the top, and update from both ends towards the other.
It was later that I realized one could actually do prefix sum instead, and that makes the code a lot simpler. For simplicity, although I did not use prefix sum in my code, I would write with prefix sum here:
pfx[ i ][ j ] : Sigma{ S[ i ][ k ], 0 ≤ k < j }
dp[ i ][ j ] : At floor i, finishing at room j, current maximum score
Assuming best transition dp[ i ][ k ] satisfies k < j:
dp[ i ][ j ] = max{ dp[ i - 1 ][ k ] + S[ i ][ j ] + pfx[ i ][ j ] - pfx[ i ][ k ], j - A ≤ k ≤ j }
Then assume k > j ...
It is obvious that the transition can be achieved in amortized O( 1 ) with proper application of deque optimization.

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

typedef vector< int > vi;

template< class T1, class T2 >
int upmax( T1 &x, T2 v ){
  if( x >= v ) return 0;
  x = v;
  return 1;
}

const int MAXN = 15;
const int MAXM = ( int ) 1e5;

int T;

const int INF = 0x3f3f3f3f; 

int N, M, X, A;
int G[ MAXN ][ MAXM ];

void init(){
  cin >> N >> M >> X >> A;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < M; ++j ){
      cin >> G[ i ][ j ];
    }
  }
}

int dp[ 2 ][ MAXM ];
 
void solve(){
  for( int i = 0; i < M; ++i ){
    dp[ 0 ][ i ] = -INF;
  }
  dp[ 0 ][ X - 1 ] = 0;
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j < M; ++j ){
      dp[ ~i & 1 ][ j ] = dp[ i & 1 ][ j ] + G[ i ][ j ];
    }
    deque< pair< int, int > > dq;
    int tag = 0;
    for( int j = 0; j < M; ++j ){
      tag += G[ i ][ j ];
      while( not dq.empty() and j - dq.front().second > A ){
        dq.pop_front();
      }
      while( not dq.empty() and dq.back().first + tag <= dp[ i & 1 ][ j ] + G[ i ][ j ] ){
        dq.pop_back();
      }
      dq.emplace_back( dp[ i & 1 ][ j ] - tag + G[ i ][ j ], j );
      upmax( dp[ ~i & 1 ][ j ], dq.front().first + tag );
    }
    dq.clear();
    tag = 0;
    for( int j = M - 1; j >= 0; --j ){
      tag += G[ i ][ j ];
      while( not dq.empty() and dq.front().second - j > A ){
        dq.pop_front();
      }
      while( not dq.empty() and dq.back().first + tag <= dp[ i & 1 ][ j ] + G[ i ][ j ] ){
        dq.pop_back();
      }
      dq.emplace_back( dp[ i & 1 ][ j ] - tag + G[ i ][ j ], j );
      upmax( dp[ ~i & 1 ][ j ], dq.front().first + tag );
    }
  }
  cout << *max_element( dp[ N & 1 ], dp[ N & 1 ] + M ) << endl;
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> T;
  for( int ti = 0; ti < T; ++ti ){
    init();
    solve();
  }
  return 0;
}