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<bits/stdc++.h>
using namespace std;
int dp[810][810];
int main(void)
{
	int d,n,i,j,k,sel[810],a[810],b[810],c[810],data,mx=-1;
	cin>>d>>n;
	for(i=1;i<=d;i++) cin>>sel[i];
	for(i=1;i<=n;i++) cin>>a[i]>>b[i]>>c[i];
	for(i=1;i<=d;i++) for(j=1;j<n;j++) dp[i][j]=0;
	for(i=1;i<=d;i++) {
		for(j=1;j<=n;j++) {
			if(a[j]<=sel[i]&&sel[i]<=b[j]) {
				for(k=1;k<=n;k++) {
					if(a[k]<=sel[i+1]&&sel[i+1]<=b[k]) {
						data=abs(c[j]-c[k]);
					}
					dp[i+1][k]=max(dp[i][j]+data,dp[i+1][k]) ;
				}
			}
		}
	}
	for(i=1;i<=n;i++) mx=max(mx,dp[d][i]);
	cout<<mx<<endl;
}

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

int main(){
	int D,N;
	int Kion[200];
	int Fmin[200],Fmax[200],Fhad[200];
	cin>>D>>N;
	for(int i=0;i<D;i++){
		cin>>Kion[i];
	}
	for(int i=0;i<N;i++){
		cin>>Fmin[i]>>Fmax[i]>>Fhad[i];
	}

	int Kekka[200][200];
	int rinji,rin2;
	//1??\???
	for(int i=0;i<N;i++){
		if(Kion[0]>=Fmin[i]&&Kion[0]<=Fmax[i]) Kekka[0][i]=0;
		else Kekka[0][i]=-1;
	}
	//2??\?????\???
	for(int day=1;day<D;day++){
		for(int fuku=0;fuku<N;fuku++){
			if(Kion[day]>=Fmin[fuku]&&Kion[day]<=Fmax[fuku]){
				rinji=-1;rin2=0;
				for(int mf=0;mf<N;mf++){
					if(Kekka[day-1][mf]!=-1&&rinji<abs(Fhad[mf]-Fhad[fuku])) {rinji=abs(Fhad[mf]-Fhad[fuku]);rin2=mf;}
				}
				Kekka[day][fuku]=Kekka[day-1][rin2]+rinji;
			}
			else{
				Kekka[day][fuku]=-1;
			}
		}
	}
	rinji=0;
	for(int i=0;i<N;i++){
		rinji=max(rinji,Kekka[D-1][i]);
	}
	cout<<rinji<<endl;
	return 0;
}

C++: #include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
	int a[200][100];
	int i2,i,n, m,o[200], x[200], y[200], z[200],i3;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++)
		scanf("%d", &o[i]);
	for (i = 1; i <= m; i++)
		scanf("%d %d %d", &x[i], &y[i], &z[i]);
	for (i = 0; i <= n; i++)
	for (i2 = 0; i2 <= m; i2++)
		a[i][i2] = -1;
	for (i = 1; i <= m; i++){
		if (o[1] >= x[i] && o[1] <= y[i]){
			a[1][i] = 0;
		}	
	}

	for (i = 1; i <= n; i++){
		for (i2 = 1; i2 <= m; i2++){
			if (a[i][i2] >= 0){
				for (i3 = 1; i3 <= m; i3++){
					if (o[i + 1] >= x[i3] && o[i + 1] <= y[i3])
						a[i + 1][i3] = max(a[i][i2] + abs(z[i2] - z[i3]), a[i + 1][i3]);


				}
			}
		}
	}
		/*for (i = 1; i <= n; i++){
			for (i2 = 1; i2 <= m; i2++){
				printf("%3d", a[i][i2]);
			}
			printf("\n");
		}*/
		int ma = 0;
		for (i = 1; i <= m; i++){
			if (a[n][i] > ma)
				ma = a[n][i];
		}
		printf("%d\n", ma);
	
}

C++: #include<stdio.h>

int n,d;
int dp[205][205];
//dp[a][b] .. a日目にb番目の服を着るような状態のうち、得られる得点の最大値。着れなければ十分小さい数

int hukup[205];
int hukdw[205];
int hukha[205];
int ond[205];


int inf = -1000000;

int abs(int p){
	if(p<0)return -p;
	else return p;
}

int max(int p,int q){
	if(p<q)return q;
	return p;
}

int main(void){
	scanf("%d%d",&d,&n);
	for(int i=1;i<=d;i++){
		scanf("%d",&ond[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&hukdw[i],&hukup[i],&hukha[i]);
	}
	//入力の受付ここまで
	
	for(int j=1;j<=n;j++){
		if(hukdw[j]<=ond[1] && ond[1]<=hukup[j]){
			dp[1][j] = 0;
		}
		else{
			dp[1][j] = inf;
		}
	}
	//初日を初期化。
	
	for(int i=2;i<=d;i++){
		for(int j=1;j<=n;j++){
			//i日目に、j番目の服を着るときの最大値
			if(hukdw[j]<=ond[i] && ond[i]<=hukup[j]){
				//着られる
				dp[i][j]=0;
				for(int k=1;k<=n;k++){
					//現在の最大値と、(前日にkを着て、今日jを着るようなパターン) のうち、大きい方をとっていく
					dp[i][j] = max(dp[i][j] , dp[i-1][k] + abs(hukha[j]-hukha[k]) );
				}
			}
			else{
				//着られない
				dp[i][j] = inf;
			}
		}
	}
	
	int ans = 0;
	for(int j=1;j<=n;j++){
		//最終日のうちの、最大値
		ans = max(ans,dp[d][j]);
	}
	printf("%d\n",ans);
	return 0;
}

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+1][i3]);
					}
				}
			}
		}
	}
		int maxv=0;
		for (int i = 0; i <= m; i++){
			maxv = max(maxv, dp[n][i]);
		}
		cout << maxv << endl;
}

C++: #include <bits/stdc++.h>
using namespace std;

#define llong long long 
typedef struct data{
	int low;
	int high;
	int eva;
}data;
int D, N;
int temp[201];
data kind[200];
int score[201][200];

int solve(int d, int k, int e){
	// cout << d << " " << k << " " << e << "   " << score[d][k] << endl;
	if(score[d][k] > e) return 0;
	score[d][k] = e;
	if(d == D) return score[d][k] = e;

	int ret = 0;
	for(int i = 0; i < N; i++){
		data use = kind[i];
		if(use.low > temp[d + 1] || use.high < temp[d + 1]) continue;
		int nexte = e + fabs(use.eva - kind[k].eva);
		if(d > 0)ret = max(ret, solve(d + 1, i, nexte));
		else ret = max(ret, solve(d + 1, i, e));
	}

	return ret;
}

int main(){
	fill_n(temp, 201, -1);
	fill_n(*score, 201 * 200, -1);
	cin >> D >> N;
	for(int i = 1; i <= D; i++){
		cin >> temp[i];
	}
	for(int i = 0; i < N; i++){
		cin >> kind[i].low >> kind[i].high >> kind[i].eva;
	}

	cout << solve(0, 0, 0) << endl;
	return 0;
}

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

 int master(int data){
 if(data>=0)
	 return data;
 return -data;
 }
int main(){
    int D,N,T[200],A[200][3];
    int dp[200][101];
    cin >> N >> D ;
    for(int i=0;i<N;i++){
        cin >>T[i];
    }
    for(int i=0;i<D;i++){
        for(int j=0;j<3;j++){
            cin >>A[i][j];
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<200;j++){
            dp[i][j]=-9999;
        }
    }
    for(int l=0;l<D;l++){
        if(T[0]>A[l][0] && T[0]<A[l][1] ){
            dp[ 0 ][ A[l][2] ]=0;
             
 
        }
    }
    for(int i=1;i<N;i++){
        for(int j=0;j<D;j++){
            if(T[i]>=A[j][0] && T[i]<=A[j][1] ){
                for(int l=0;l<=100;l++){
                    if(dp[i-1 ][ l ]>=0)
                        dp[ i ][ A[j][2] ]=max(dp[ i ][ A[j][2] ],dp[ i-1 ][ l ]+master(l-A[j][2]));//テッツセツεッツスツ、テッツセツづッツスツサテッツセツづァツ板佚ッツスツ」テッツセツ?テッツスツセテッツセツεッツスツ」テッツセツ?テッツスツァテッツセツεッツスツ」テッツセツ?テッツスツョテッツセツεッツスツヲテッツセツづヲツ??テッツスツゥテッツセツづッツスツォテッツセツづ、ツスツ堙ッツスツ」テッツセツ??テッツスツ、テッツセツづッツスツサテッツセツづァツ板佚ッツスツ・テッツセツづ・ツエツ「?
                     
 
                }
            }
        }
    }
    int answer=0;
    for(int j=0;j<101;j++)
    {
		
        answer=max(answer,dp[ N-1 ][j]);
    }
    cout << answer << endl;
    return 0;
}