Submission #1356472

---

Source Code Expand

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define GREY 2
#define WHITE 1
#define BLACK 0

ll  maximum=-1,d, k, tenki[20001], maxi[20000] = { -1 }, mini[20001], dp[2][201] = { -1 }, go = 0;
ll DP(ll n, ll previous,ll mai) {	
	if (n == d) { return 0; }
	if (n == 0) {
		return max(DP(n + 1, maxi[tenki[n]], 0), DP(n + 1, mini[tenki[n]], 1));
	}
	if (dp[mai][n]>=0) { return dp[mai][n]; }
	return dp[mai][n]=max(DP(n + 1, maxi[tenki[n]],   0)+abs(previous - maxi[tenki[n]]),DP(n + 1, mini[tenki[n]],1)+abs(previous - mini[tenki[n]]));
}

int main()
{
	REP(i, 2) {
		REP(j, 201) { dp[i][j] = -1; }
	}
	memset(maxi, -1, sizeof(maxi));
	REP(i, 20001) { mini[i] = 100000; }
	cin >> d >> k;
	REP(i, d) {
		cin >> tenki[i];
	}
	REP(i, k) {
		ll mi, ma, c;
		cin >> mi >> ma >> c;
		FOR(j, mi, ma + 1) {
			maxi[j] = max(maxi[j], c);
			mini[j] = min(mini[j], c);
		}
	}
	cout <<DP(0, 0,0) << endl;
	return 0;
}

Submission Info

Judge Result