JOI 12 本選 Hot days ( DP )

Hot days | Aizu Online Judge
dp[ i ][ j ]: After considering clothe for day i, which is of c_i = j, maximum value

#include <bits/stdc++.h>
using namespace std;
const int MAXD = 200 + 2;
const int MAXN = 200 + 2;
const int MAXT = 60 + 6;
const int MAXAB = MAXT;
const int MAXC = 100 + 2;

void upmax(int &x, int v){ if( x < v ) x = v; }

int d, n;
int t[ MAXD ];
int a[ MAXN ], b[ MAXN ], c[ MAXN ];

int dp[ MAXD ][ MAXC ];

void solve(){
    for(int i = 1; i <= d; ++i)
        for(int j = 0; j < MAXC; ++j)
            dp[ i ][ j ] = -(int)( 1e9 );
    for(int i = 0; i < d; ++i)
        for(int j = 0; j < MAXC; ++j){
            for(int k = 1; k <= n; ++k)
                if( a[ k ] <= t[ i + 1 ] && t[ i + 1 ] <= b[ k ] ){
                    if( i == 0 ) dp[ i + 1 ][ c[ k ] ] = 0;
                    else upmax( dp[ i + 1 ][ c[ k ] ], dp[ i ][ j ] + abs( j - c[ k ] ) );
                }
        }
    int ans = 0;
    for(int j = 0; j < MAXC; ++j)
        upmax( ans, dp[ d ][ j ] );
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &d, &n);
    for(int i = 1; i <= d; ++i)
        scanf("%d", &t[ i ]);
    for(int i = 1; i <= n; ++i)
        scanf("%d%d%d", &a[ i ], &b[ i ], &c[ i ]);
    solve();
    return 0;
}