HE Zulu visits Wonderland ( DP )

https://www.hackerearth.com/challenge/competitive/may-circuits-17/algorithm/zulu-visits-wonderla-1/

題意：
N 層的地下迷宮，M 種物品。
在時間 x，你能拿第 i 個物品若且唯若所有 Level 比 Level[ i ] 小的物品的過期時間不早於 x，並且 x + Time[ i ] 不晚於 E[ i ]。
問最大總價值。

制約：
1≤N,M≤2000
1≤Value≤1e9
1≤Time,E[i]≤2000
1 ≤ Level[ i ] ≤ N

解法：
優先考慮早過期的物品，倒著時間進行動態規劃。

複雜度：
O( M * MAXT )

#include <bits/stdc++.h>
using namespace std;
 
template< class T1, class T2 >
int upmax( T1 &x, T2 v ) {
  if( x >= v ) return 0;
  x = v;
  return 1;
}
 
const int MAXN = 2000;
const int MAXM = 2000;
const int MAXV = int( 1e9 );
const int MAXT = 2000;
 
int N, M;
int E[ MAXN ];
int pme[ MAXN + 1 ];
int V[ MAXM ], T[ MAXM ], L[ MAXM ];
int ord[ MAXM ];
 
long long dp[ MAXT + 1 ];
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  pme[ 0 ] = 0x3f3f3f3f;
  for( int i = 0; i < N; ++i ) {
    cin >> E[ i ];
    pme[ i + 1 ] = min( pme[ i ], E[ i ] );
  }
  for( int i = 0; i < M; ++i ) {
    cin >> V[ i ] >> T[ i ] >> L[ i ];
    --L[ i ]; // 0 idx
    ord[ i ] = i;
  }
  auto st = [ & ]( int x ) { return min( E[ L[ x ] ], pme[ L[ x ] ] ); };
  sort( ord, ord + M, [ & ]( int i, int j ) { return st( i ) > st( j ); } );
  for( int i = 0; i < M; ++i ) {
    long long maxt = 0;
    for( int j = MAXT; j >= st( ord[ i ] ); --j ) {
      upmax( maxt, dp[ j ] );
    }
    for( int j = st( ord[ i ] ); j >= T[ ord[ i ] ]; upmax( maxt, dp[ --j ] ) ) {
      upmax( dp[ j - T[ ord[ i ] ] ], maxt + V[ ord[ i ] ] );
    }
  }
  cout << *max_element( dp, dp + MAXT + 1 ) << endl;
  return 0;
}