Submission #1338473

---

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  d, k, tenki[201], maxi[200] = { -1 }, mini[201], dp[200] = { -1 };

ll DP(ll n, ll suuchi) {
	if (n == d) { return 0; }
	if (dp[n] >= 0) {return dp[n]; }//cout << n << " " << suuchi << endl;
	if (n == 0) {
		return  max(DP(n + 1, mini[tenki[n]]), DP(n + 1, maxi[tenki[n]]));
	}
	//cout<< suuchi - maxi[tenki[n]]<<endl;
	return dp[n] = max({ DP(n + 1, maxi[tenki[n]]) + abs(maxi[tenki[n - 1]] - maxi[tenki[n]]), DP(n + 1, mini[tenki[n]]) + abs(mini[tenki[n - 1]] - mini[tenki[n]]) ,DP(n + 1, mini[tenki[n]]) + abs(mini[tenki[n - 1]] - maxi[tenki[n]]), DP(n + 1, mini[tenki[n]]) + abs(maxi[tenki[n - 1]] - mini[tenki[n]]) });
}


int main()
{
	memset(dp, -1, sizeof(dp));
	memset(maxi, -1, sizeof(maxi));
	REP(i, 201) { 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)<<endl;
	//cout << maxi[tenki[0]] << endl;
	/*int ma= DP(0, maxi[tenki[0]]);
	memset(dp, -1, sizeof(dp));
	int mi = DP(0, mini[tenki[0]]);
	cout << max(ma, mi) << endl;*/
	return 0;
}

Submission Info

Judge Result