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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<sstream>
#include<utility>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
#include<set>
#define MV 505
using namespace std;
typedef pair<int,int>P;
int W,H,N,Cs[2],Ce[2],i,j,k,X,Y,T,c1=0,c2=0,G[MV][MV]={0},V[MV][MV],v[MV][MV],d[MV][MV],mx[4]={0,0,1,-1},my[4]={1,-1,0,0};//D,U,R,L
char S[1005],mp[255];
int main()
{
	mp['D']=0;mp['U']=1;mp['R']=2;mp['L']=3;
	scanf("%d%d%d",&W,&H,&N);
	scanf("%d%d%d%d",Cs,Cs+1,Ce,Ce+1);
	for(i=0;i<N;i++)
	{
		scanf("%d%d",&X,&Y);
		scanf("%d%s",&T,S);
		for(j=0;j<T;j++)
		{
			for(k=0;k<strlen(S);k++)
			{
				int nx=X+mx[mp[S[k]]];
				int ny=Y+my[mp[S[k]]];
				if(nx<0||nx>=W||ny<0||ny>=H)continue;
				if(nx==X)V[nx][max(ny,Y)]++;
				else G[max(nx,X)][ny]++;
				X=nx;
				Y=ny;
			}
		}
	}
	for(int i=0;i<=W;i++)for(int j=0;j<=H;j++)d[i][j]=999999999;
	d[Cs[0]][Cs[1]]=0;
	priority_queue<pair<int,P> >Q;
	Q.push(make_pair(0,make_pair(Cs[0],Cs[1])));
	for(;Q.size();)
	{
		P np=Q.top().second;
		int nxc=-Q.top().first;
		Q.pop();
		if(v[np.first][np.second])continue;
		v[np.first][np.second]=1;
		for(i=0;i<4;i++)
		{
			int ny=np.second+my[i];
			int nx=np.first+mx[i];
			int nc=0;
			if(nx==np.first)nc=G[nx][min(ny,np.second)];
			else nc=V[min(nx,np.first)][ny];
			if(nx<0||nx>W||ny<0||ny>H||v[nx][ny]||d[nx][ny]<=nxc+nc)continue;
			d[nx][ny]=nxc+nc;
			Q.push(make_pair(-d[nx][ny],make_pair(nx,ny)));
		}
	}
	printf("%d\n",d[Ce[0]][Ce[1]]);
	return 0;
}

C++: #include<iostream>
#include<cmath>
#define MINF -1e9
using namespace std;

struct cloth
{
  int hi,lo,point;
};

int dp[201][201];

int main(){
  int d,n;
  cin >> d >> n;
  int t[d];
  cloth *c;
  c = new cloth[n];
  for(int i = 0; i < d; i++){
    cin >> t[i];
  }
  for(int i = 0; i < n; i++){
    cin >> c[i].lo >> c[i].hi >> c[i].point;
  }

  for(int i = 0; i < n; i++){
    if(c[i].lo <= t[0] && t[0] <= c[i].hi){
    }else{
      dp[0][i] = MINF;
    }
  }

  for(int i = 1; i < d; i++){
    for(int j = 0; j < n; j++){
      for(int k = 0; k < n; k++){
	if(c[j].lo <= t[i] && t[i] <= c[j].hi){
	  dp[i][j] = max(dp[i][j],
			 dp[i-1][k] + abs(c[k].point - c[j].point));
	}else{
	  dp[i][j] = MINF;
	}
      }
    }
  }
  int res = 0;
  for(int i = 0; i < n; i++){
    res = max(dp[d - 1][i], res);
  }
  
  // for(int i = 0; i < d; i++){
  //   for(int j = 0; j < n; j++){
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  
  cout << res << endl;
  return 0;
}

C++: #include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define int long long
static const int INF = 8931919114514810;
static const int MAX_N = 300;
using namespace std;

int A[300],B[300],C[300];
int mem[MAX_N][MAX_N];
int N,D;
int Day[MAX_N];
int cal(int day,int pp){
   int res=mem[day][pp];
   if(day==N+1){
        return res=0;
   }
   if(mem[day][pp]!=-1){
        return res;
   }
   if(day<=1){
       FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
            res=cal(day+1,C[i]);
         }
      }
   }
   else{
        FOR(i,1,D){
            if(Day[day]>=A[i]&&Day[day]<=B[i]){
                int temp=abs(pp-C[i]);
                res=max(cal(day+1,C[i])+temp,res);
                mem[day][pp]=res;
            }
        }
   }
   return mem[day][pp]=res;
}

signed main(){
    cin>>N>>D;
    memset(mem,-1,sizeof(mem));
    FOR(i,1,N){
        cin>>Day[i];
    }
    FOR(i,1,D){
        cin>>A[i]>>B[i]>>C[i];
    }
    int ans=0;
    for(int i=1;i<=D;++i){
        if (Day[1] < A[i]|| Day[1] > B[i]) continue;
        ans=max(cal(1,C[i]),ans);
    }
    cout<<ans<<endl;
    return 0;
}

C++: //
//  main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct status{
	int toptemp;
	int bottomtemp;
	int fancy;
	
};

int main(){	
	int D,N;
	cin >> D >> N;
	status dress[201];
	int temp[201];
	for(int i=0;i<D;i++){
		cin >> temp[i];
	}
	for(int i=0;i<N;i++){
		cin >> dress[i].bottomtemp >> dress[i].toptemp >> dress[i].fancy;
	}
	
	int dp[201][201];//i??\???????????????j????????????????????§????´???????
	for(int i=0;i<201;i++){
		for(int j=0;j<201;j++){
			dp[i][j] = -1;
		}
	}
	
	for(int i=0;i<N;i++){//0??\?????????????¨???????
		if(temp[0] >= dress[i].bottomtemp && temp[0] <= dress[i].toptemp){
			dp[0][i] = dress[i].fancy;
		}
	}
	
	for(int i=1;i<D;i++){
		for(int j=0;j<N;j++){
			if(temp[i] >= dress[j].bottomtemp && temp[i] <= dress[j].toptemp){//i??\??????j??????????????????
				int Maxfancy=-1;
				for(int k=0;k<N;k++){//i-1??\????????¨????????????????????´???????????????????´???????????????§???????????????????????????
					if(dp[i-1][k] == -1)continue;
					Maxfancy = max(Maxfancy,abs(dress[j].fancy - dress[k].fancy));
				}
				dp[i][j] = Maxfancy;
			}
		}
	}
	
	int answer = 0;
	for(int i=1;i<D;i++){
		int Max = -1;
		for(int j=0;j<N;j++){
			Max = max(Max,dp[i][j]);
		}
		answer += Max;
	}
	cout << answer << endl;
	/*
	vector<int> dresses;
	int matrix[201][2];
	for(int i=0;i<D;i++){
		for(int j=0;j<N;j++){
			if(temp[i] >= dress[j].bottomtemp && temp[i] <= dress[j].toptemp){
				dresses.push_back(dress[j].fancy);
			}
		}
		sort(dresses.begin(),dresses.end());
		matrix[i][0] = dresses[0];
		matrix[i][1] = dresses[dresses.size() - 1];
	}
	
	int dp[201]={};
	dp[0] = max(matrix[0][0],matrix[0][1]);
	
	for(int i=1;i<D;i++){
		dp[i] = max(abs(dp[i-1] - matrix[i][0]),abs(dp[i-1] - matrix[i][1]));
	}
	
	cout << dp[D-1] << endl;
	*/
	return 0;
}

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

int main(){
	int d,n,t[200],a[200],b[200],c[200];
	int dp[201][200] = {};
	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];
	for(int i = 1;i <= d;i++){
		for(int j = 0;j < n;j++){
			if(a[j] <= t[i - 1] && t[i - 1] <= b[j]){
				for(int k = 0;k < n;k++){
					if(i >= 2 && a[k] <= t[i - 2] && t[i - 2] <= b[k]) dp[i][j] = max(dp[i][j],dp[i - 1][k] + abs(c[j] - c[k]));
				}
			}
		}
	}
	int ma = 0;
	for(int i = 0;i < n;i++) ma = max(ma,dp[d][i]);
	cout << ma << endl;
	return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int n,m,a[201],b[3][201];
int mem[200][20000];
int hot(int day,int bef);

int main(){

  cin >> n >> m;

  memset(mem,-1,sizeof(mem));

  for(int i=0;i<n;i++) cin >> a[i];
  for(int i=0;i<m;i++) cin >> b[0][i] >> b[1][i] >> b[2][i];

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

int hot(int day,int bef){
  int ret=0;
  if(mem[day][bef] != -1) return mem[day][bef];
  if(day < n){
    for(int i=0;i<m;i++){
      if(a[day]>=b[0][i]&&a[day]<=b[1][i]){
	if(day==0){
	  ret=max(ret,hot(day+1,b[2][i]));
	}else{
	  ret=max(ret,hot(day+1,b[2][i])+(int)fabs((double)bef-b[2][i]));
	}
	
      }
    }
  }
  return mem[day][bef] = ret;
}