# 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;
}
```