Go: ///
// File:  0579.go
// Author: ymiyamoto
//
// Created on Mon Mar 19 18:46:50 2018
//
package main

import (
	"fmt"
)

var D, N int

type cloth struct {
	A, B, C int
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	fmt.Scan(&D, &N)
	thermals := make([]int, D+1)

	for i := 1; i <= D; i++ {
		fmt.Scan(&thermals[i])
	}

	clothes := make([]cloth, N)
	for i := 0; i < N; i++ {
		fmt.Scan(&clothes[i].A, &clothes[i].B, &clothes[i].C)
	}

	dp := make([][]int, D+1)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := 0; i < D; i++ {
		for j := 0; j < N; j++ {
			for k := 0; k < N; k++ {
				t1 := thermals[i]
				t2 := thermals[i+1]
				if clothes[j].A <= t2 && t2 <= clothes[j].B && clothes[k].A <= t1 && t1 <= clothes[k].B {
					dp[i+1][j] = max(dp[i+1][j], dp[i][k]+abs(clothes[j].C-clothes[k].C))
				}
			}
		}
	}

	val := 0
	for _, v := range dp[D] {
		val = max(val, v)
	}

	fmt.Println(val)
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()

#define PI acos(-1.0)
#define INF 1000000007

typedef long long ll; 
typedef pair<ll, ll> PL;

ll n, d, p = 0, dp1, dp2;
ll t[1000], a[1000], b[1000], c[1000], MAX[1000], MIN[1000];

int main(){
	cin >> d >> n;
	REP(i, d){
		cin >> t[i];
	}
	REP(i, n){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, d){
		ll ma = -1, mi = 10000;
		REP(j, n){
			if (t[i] >= a[j] && t[i] <= b[j]){
				ma = max(c[j], ma);
				mi = min(c[j], mi);
			}
		}
		MAX[i] = ma;
		MIN[i] = mi;
	}
	dp1 = MAX[0];
	dp2 = MIN[0];
	REP(i, d - 1){
		if (abs(MAX[i + 1] - dp2) >= abs(MIN[i + 1] - dp1)){
			p += abs(MAX[i + 1] - dp2);
			if (abs(MAX[i + 1] - dp2) == abs(MIN[i + 1] - dp1)){
				dp1 = MAX[i + 1];
				dp2 = MIN[i + 1];
			}
			else{
				dp1 = dp2 = MAX[i + 1];
			}
		}
		else{
			p += abs(MIN[i + 1] - dp1);
			dp1 = dp2 = MIN[i + 1];
		}
	}
	cout << p << endl;
}

C++: #include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
int main()
{
	int n, m, t[1001], c[100],c2[101],v[100],dp[1001][100];
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> t[i];
	for (int i = 1; i <= m; i++){
		cin >> c[i] >> c2[i] >> v[i];
	}
	memset(dp, -1, sizeof(dp));

	for (int i = 1; i <= m; i++){
		if (t[1] >= c[i] && t[1]<=c2[i])
			dp[1][i] = 0;
	}

	for (int i = 1; i <= n; i++){
		for (int i2 = 1; i2 <= m; i2++){
			if (dp[i][i2] >= 0){
				for (int i3 = 1; i3 <= m; i3++){
					if (t[i + 1] >= c[i3] && t[i + 1] <= c2[i3]){
						dp[i + 1][i3] = max(dp[i][i2] + abs(v[i2] - v[i3]), dp[i][i3]);
					}
				}
			}
		}
	}
		int maxv=0;
		for (int i = 0; i <= m; i++){
			maxv = max(maxv, dp[n][i]);
		}
		cout << maxv << endl;
}

C++: /*
     こういうやるだけDPしか出なければいいのに
     あw頭ついてないからそれでも予選落ち確定でしたw
 */

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

#define INF 0x7fffffff

int d;
int n;
int a[200];
int b[200];
int c[200];
int t[200];
int dp[200][200]; // dp[day][used]
int ans;

int main() {
    scanf("%d %d", &d, &n);

    for (int i=0; i<d; i++) {
        scanf("%d", &t[i]);
    }

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

    for (int i=0; i<n; i++) {
        if (t[0] < a[i] || b[i] < t[0]) dp[0][i] = -INF;
    }

    for (int i=1; i<d; i++) {
        for (int j=0; j<n; j++) {
            if (t[i] < a[j] || b[j] < t[i]) continue;
            for (int k=0; k<n; k++) {
                int val;

                if (dp[i-1][k] < 0) continue;
                val = dp[i-1][k] + abs(c[j] - c[k]);
                dp[i][j] = max(dp[i][j], val);
            }
        }
    }

    for (int i=0; i<n; i++) {
        ans = max(ans, dp[d-1][i]);
    }

    printf("%d\n", ans);
}

C++: #include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int INF = -1000000000;

int main(){
  int d,n,a[200],b[200],c[200],t[200];
  scanf("%d %d",&d,&n);
  for(int i=0;i<d;i++) scanf("%d",t+i);
  for(int i=0;i<n;i++) scanf("%d %d %d",a+i,b+i,c+i);
  int dp[201][200];
  fill(dp[0],dp[0]+200,INF);
  for(int i=0;i<d;i++){
    for(int j=0;j<n;j++){
      if(i==0&&a[j]<=t[i]&&t[i]<=b[j]){
        dp[i][j] = 0;
        continue;
      }
      for(int k=0;k<n;k++){
        if(a[j]<=t[i]&&t[i]<=b[j]){
          dp[i][j] = max(dp[i][j],dp[i-1][k]+max(c[j],c[k])-min(c[j],c[k]));
        }
      }
    }
  }
  int ans = 0;
  for(int i=0;i<n;i++) ans = max(ans,dp[d-1][i]);
  printf("%d\n",ans);
  return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
	int d,n;
	cin >> d >> n;
	int dp[205][105];
	for(int i=0;i<205;i++)for(int j=0;j<205;j++)dp[i][j]=1e7;
	int temp[205];
	int a[205],b[205],c[205];
	for(int i=1;i<=d;i++)
	{
		cin >> temp[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin >> a[i]>> b[i] >> c[i];
		if(a[i] <= temp[1] && temp[1] <= b[i])
		{
			dp[1][c[i]]=min(dp[1][c[i]],0);
		}
	}
	for(int i=2;i<=d;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[j] <= temp[i] && temp[i] <= b[j])
			{
				for(int k=0;k<=100;k++) dp[i][c[j]]=min(dp[i][c[j]],dp[i-1][k]+abs(k-c[j]));
			}
		}
	}
	int val=1e7;
	for(int k=0;k<=100;k++) val=min(val,dp[d][k]);
	cout << val << endl;
}

C++: #include <iostream>
#include <algorithm>
using namespace std;

const int MAX_D = 210;
const int MAX_N = 210;
int t[MAX_D];
int a[MAX_N], b[MAX_N], c[MAX_N];
int dp[MAX_D][MAX_N];	// ??\??????????????????

int d, n;

int func(int day, int before){
	if(day >= d) return 0;
	int res = 0;
	for(int i = 0; i < n; ++i){
		if(a[i] <= t[day] && t[day] <= b[i]){
			int score = before - c[i];
			if(score < 0) score = -score;
			res = max(res, score + func(day + 1, c[i]));
		}
	}
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> d >> n;
	
	for(int i = 0; i < d; ++i){
		cin >> t[i];
	}
	
	for(int i = 0; i < n; ++i){
		cin >> a[i] >> b[i] >> c[i];
	}
	
	int ans = 0;
	for(int i = 0; i < n; ++i){
		if(a[i] <= t[0] && t[0] <= b[i])
			ans = max(ans, func(1, c[i]));
	}
	
	cout << ans << endl;
	//cout << func(0, 0) << endl;
	
	return 0;
}

C++: #include<iostream>

int d,n,t[201],data[201][2],dp[201][2];

int main(){
	std::cin>>d>>n;
	for(int i=0;i<d;i++)std::cin>>t[i],data[i][1]=1000000;
	for(int i=0;i<n;i++){
		int a,b,c;
		std::cin>>a>>b>>c;
		for(int j=0;j<d;j++){
			if(a<=t[j]&&t[j]<=b)data[j][0]=std::max(data[j][0],c),data[j][1]=std::min(data[j][1],c);
		}
	}
	for(int i=0;i<d-1;i++){
		for(int j=0;j<2;j++){
			dp[i][j]=std::max(dp[i-1][0],dp[i-1][1])+std::max(abs(data[i][j]-data[i+1][0]),abs(data[i][j]-data[i+1][1]));
		}
	}
	std::cout<<std::max(dp[d-2][0],dp[d-2][0])<<std::endl;
	return 0;
}

C++: #include<bits/stdc++.h>
#define LL long long
#define FOR(i,a,b) for(int i=a;i<=b;++i)

using namespace std;

static const LL MAX_N = 1e+5;
static const LL INF = 1 << 25;

struct clothes{
    LL A[150],B[150],C[150];
};

int N,D;
LL res=-INF;
LL Day[150];
LL mem[250][110][110];
clothes T;

LL cal(LL day,LL p,LL pp,LL sum){
    if(res<sum+abs(pp-p))res=sum+abs(pp-p);
    if(mem[day][p][pp]!=0)return mem[day][p][pp];
    if(day==N+1)return 0;
    if(day==0){
        FOR(i,1,D)
        if(Day[1]>=T.A[i]&&Day[1]<=T.B[i])cal(day+1,T.C[i],p,sum);
    }
    FOR(i,1,D){
        if(Day[day]>=T.A[i]&&Day[day]<=T.B[i]){
            if(day>2)cal(day+1,T.C[i],p,sum+abs(pp-p));
            else cal(day+1,T.C[i],p,sum);
        }
    }
    return mem[day][p][pp]=res;
}


int main(){
    cin>>N>>D;
    FOR(i,1,N)cin>>Day[i];
    FOR(i,1,D)
        cin>>T.A[i]>>T.B[i]>>T.C[i];
        cout<<cal(0,0,0,0)<<endl;
}