IOICJ 80 Buying Potions ( DP, Multiple Knapsack, Monotonous )

Problem Description:
There are N shops that sell potions, and each of them only sells one kind of potion. The i'th shop sells potions for P[ i ] per glass, where each glass could heal B[ i ] units of health, but has only C[ i ] glasses in stock. Besides, there is another regulation that you must buy either none or at least K glasses of potion in each store. You have X units of money, what is the maximum units of health you could cure in total?

Constraints:
1≤T≤100
1≤N≤100
1≤K≤x≤3e4
1≤pi≤x
1≤bi≤1e9
K≤ci≤x
At most 10 tests do not satisfy: N ≤ 30 and x ≤ 100

Sample Input:
3
3 2 5
3 514 4
2 3 2
1 1 5
3 1 5
3 514 4
2 3 2
1 1 5
2 1 10
5 1 4
4 2 1

Sample Output:
6
517
3

Solution:
It clear that it is a multiple knapsack problem. However, with the constraint that it is forbidden to buy [ 1, K ) number of potions in any of the stores, it is difficult to be solved with the classical algorithm using binary enumeration. Let's consider the O( NW ) algorithm that exploits the property of monotonicity. This blog helped a lot in my understanding the algorithm. Let h( i, m ) denote maximum units of health that can be obtained after considering the first i elements, and having used money m in total. We know that the transition is h( i, m ) = max{ h( i - 1, m - k * P[ i ] ) + k * B[ i ], 0 ≤ k ≤ min( C[ i ], m / P[ i ] ) }. We could observe that the second parameter of function h could actually be seen as several deques differentiated by m modulo P[ i ].
Let m = k * P[ i ] + r, where 0 ≤ r < P[ i ]:
f( i, m )
= max{ f( i - 1, j * P[ i ] + r ) + ( k - j ) * B[ i ], 0 ≤ j ≤ k }
= max{ f( i - 1, j * P[ i ] + r ) - j * B[ i ], 0 ≤ j ≤ k } + k * B[ i ]
Therefore, in each modulo-differentiated ( r ) deques, when we emplace a possible transfer source f( i, m ) in, we would instead emplace f( i, m ) - m / P[ i ] * B[ i ], and in return when some value x taken from the deque is about to be used to update f( i, m ), we would update with x + m / P[ i ] * B[ i ] instead. With this trick, values in the deque will be independent and thus static ( no element needs to be modified along the updating process ).
And all the rest is deque classical monotonicity. I have used a second deque to maintain the actual size of decisions, for the size of the monotonic deque does not imply the actual size of decisions.

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

typedef vector< int > vi;
typedef vector< vi > vvi;

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

const int INF = 0x3f3f3f3f;

const int MAXN = 100;
const int MAXX = ( int ) 3e4;

int N, K, X;
int P[ MAXN ], B[ MAXN ], C[ MAXN ];

void init(){
  cin >> N >> K >> X;
  for( int i = 0; i < N; ++i ){
    cin >> P[ i ] >> B[ i ] >> C[ i ];
  }
}

ll dp[ 2 ][ MAXX + 1 ];

void preprocess(){
  for( int i = 0; i <= X; ++i ){
    dp[ 0 ][ i ] = 0;
  }
  for( int i = 0; i < N; ++i ){
    for( int j = 0; j <= X; ++j ){
      dp[ ~i & 1 ][ j ] = dp[ i & 1 ][ j ];
    }
    for( int j = 0; j < P[ i ]; ++j ){
      deque< pair< ll, int > > dq_size, dq_mono;
      for( int k = j, c = 0; k <= X; k += P[ i ], ++c ){
        if( dq_size.size() == C[ i ] - K + 1 ){ // it is only allowed to take between [ C[ i ] - K, C[ i ] ] number of potions
          if( dq_size.front() == dq_mono.front() ){
            dq_mono.pop_front();
          }
          dq_size.pop_front();
        }
        if( k - K * P[ i ] >= 0 ){
          dq_size.emplace_back( dp[ i & 1 ][ k - K * P[ i ] ] - 1LL * B[ i ] * ( c - K ), c );
          while( not dq_mono.empty() ){
            ll a; int id; tie( a, id ) = dq_mono.back();
            if( a > dp[ i & 1 ][ k - K * P[ i ] ] - 1LL * B[ i ] * ( c - K ) ) break;
            else dq_mono.pop_back();
          }
          dq_mono.emplace_back( dp[ i & 1 ][ k - K * P[ i ] ] - 1LL * B[ i ] * ( c - K ), c );
        }
        if( not dq_mono.empty() ){
          upmax( dp[ ~i & 1 ][ k ], dq_mono.front().first + 1LL * B[ i ] * c );
        }
      }
    }
  }
}

void solve(){
  cout << *max_element( dp[ N & 1 ], dp[ N & 1 ] + X + 1 ) << endl;
}

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