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 := 1; 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>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int dp[100][2][3];

int main(){
	int n,k,a[100],b[100];
	scanf("%d%d",&n,&k);
	dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=1;
	for(int i=0;i<k;i++){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=0;j<3;j++) if(b[i]!=j+1) dp[a[i]-1][0][j]=dp[a[i]-1][1][j]=-1;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			if(dp[i][0][j]==-1) continue;
			for(int k=0;k<3;k++){
				if(k==j) dp[i][1][j]=(dp[i][1][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k]))%10000;
				else dp[i][0][j]=(dp[i][0][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k])+(dp[i-1][1][k]==-1?0:dp[i-1][1][k]))%10000;
			}
		}
	}
	int res=0;
	for(int i=0;i<3;i++) res+=(dp[n-1][0][i]==-1?0:dp[n-1][0][i])+(dp[n-1][1][i]==-1?0:dp[n-1][1][i]);
	res%=10000;
	printf("%d\n",res);
}

C++: #include <cstdio>
#include <algorithm>
#include <iostream>
#define rep(i,n) for(int i = 0; i < n; i++)
#define INF 100000000
using namespace std;

int d, n;
int dp[200][200];
int t[200], a[200], b[200], c[200];

int sa(int x, int y){
	if(x > y) return x-y;
	else return y-x;
}

int main(){
	scanf("%d%d", &d, &n);
	rep(i,d) scanf("%d", &t[i]);
	rep(i,n) scanf("%d%d%d", &a[i], &b[i], &c[i]);
	for(int i = 0; i < n; i++){
		if(a[i] > t[0] || t[0] > b[i]) dp[0][i] = -1*INF;
	}
	for(int i = 1; i < d; i++){
		for(int j = 0; j < n; j++){
			if(a[j] <= t[i] && t[i] <= b[j]){
				for(int k = 0; k < n; k++){
					dp[i][j] = max(dp[i][j],dp[i-1][k]+sa(c[k],c[j]));
				}
			} else{
				dp[i][j] = -1*INF;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		ans = max(ans,dp[d-1][i]);
	}
	printf("%d\n", ans);
}

C++: #include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int a[101],b[101];
    for(int i=0;i<101;++i){
        a[i]=-1;
        b[i]=-1;
    }
    int n,m;
    cin>>n>>m;
    int *day;
    day=new int[n];
    for(int i=0;i<n;++i){
        cin>>day[i];
    }
    int **c;
    c=new int*[m];
    for(int i=0;i<m;++i){
        c[i]=new int[3];
        for(int j=0;j<3;++j){
            cin>>c[i][j];
        }
        if(c[i][0]<=day[0]&&day[0]<=c[i][1]){
            a[c[i][2]]=0;
        }
    }
    for(int i=1;i<n;++i){
        for(int j=0;j<101;++j) {
            if(a[j]>-1){
                for(int k=0;k<m;++k) {
                    if(c[k][0]<=day[i]&&day[i]<=c[k][1]){
                        b[c[k][2]]=max(a[j]+abs(j-c[k][2]),b[c[k][2]]);
                    }
                }
            }
        }
        swap(a,b);
    }
    int ans=0;
    for(int i=0;i<101;++i){
        ans=max(ans,a[i]);
    }
    cout<<ans<<endl;
    return 0;
}

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

int dp[201][61], d, n, t[61], a[201], b[201], c[201], mx = 0;

int abs(int x, int y)
{
	if (x >= y) return x - y;
	else return y - x;
}

int main()
{
	cin >> d >> n;
	for (int i = 1; i <= d; i++){
		cin >> t[i];
	}
	for (int i = 1; i <= n; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	memset(dp, -1, sizeof dp);

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

	//dp
	for (int today = 2; today <= d; today++){
		for (int n2 = 1; n2 <= n; n2++){
			for (int n1 = 1; n1 <= n; n1++){
				if (dp[today - 1][n1] == -1) continue;
				if (a[n2] > t[today] || t[today] > b[n2]) continue;
				dp[today][n2] = max(dp[today][n2], dp[today - 1][n1] + abs(c[n1], c[n2]));
			}
		}
	}

	for (int i = 1; i < n; i++){
		mx = max(dp[d][i], mx);
	}
	cout << mx << endl;
	return 0;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
struct HUKU{
	int min;
	int max;
	int point;
};
HUKU huk[250];
int day[250];
int n,m;
int memo[250][120][120];

int check(int DAY,int point,int mae)
{
	if(memo[DAY][point][mae]!=-1)return memo[DAY][point][mae];
	int ans=0;
	for(int i=0;i<m&&DAY!=n-1;i++)
	{
		if(day[DAY+1]>=huk[i].min&&day[DAY+1]<=huk[i].max)
		ans=max(check(DAY+1,huk[i].point,point),ans);
	}
	
	return memo[DAY][point][mae]=ans+max(point,mae)-min(point,mae);
	
	
	
}





int main ()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>day[i];
	for(int i=0;i<m;i++)
		cin>>huk[i].min>>huk[i].max>>huk[i].point;
	memset(memo,-1,sizeof(memo));

	int ans=0;
	for(int i=0;i<m;i++){
		if(day[0]>=huk[i].min&&day[0]<=huk[i].max)
		ans=max(ans,check(0,huk[i].point,huk[i].point));
	}
	cout<<ans<<endl;
	return 0;
}

C++: using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtTest.HCPC2019_15
{
    class D
    {
        static void Main(string[] args)
        {
            Method(args);
        }

        static void Method(string[] args)
        {
            int[] nm = ReadInts();
            int n = nm[0];
            int m = nm[1];
            int[] ts = new int[n];
            for (int i = 0; i < n; i++) ts[i] = ReadInt();
            int[][] abs = new int[m][];
            for(int i = 0; i < m; i++) abs[i] = ReadInts();

            int[,] dp = new int[n, m];
            for(int i = 0; i < m; i++)
            {
                if (abs[i][0] <= ts[0] && ts[0] <= abs[i][1]) dp[0, i] = 0;
                else dp[0, i] = -1;
            }

            for(int i = 1; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    if (ts[i] < abs[j][0] || abs[j][1] < ts[i]) dp[i, j] = -1;
                    else
                    {
                        int max = 0;
                        for(int k = 0; k < m; k++)
                        {
                            if (dp[i - 1, k] == -1) continue;

                            max = Max(max, dp[i - 1, k]
                                + Abs(abs[j][2] - abs[k][2]));
                        }
                        dp[i, j] = max;
                    }
                }
            }

            int res = 0;
            for (int i = 0; i < m; i++) res = Max(res, dp[n - 1, i]);
            WriteLine(res);
        }

        private static string Read() { return ReadLine(); }
        private static char[] ReadChars() { return Array.ConvertAll(Read().Split(), a => a[0]); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}