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;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int t[210];
int a[210];
int b[210];
int c[210];

int dp[210][210];

int main(void){
	int n,d;
	cin >> n >> d;
	for(int i=0;i<n;++i) cin >> t[i];
	for(int i=0;i<d;++i) cin >> a[i] >> b[i] >> c[i];

	for(int i=0;i<n-1;++i){
		for(int j=0;j<d;++j){
			if(t[i]<a[j]||b[j]<t[i])
				continue;
			for(int k=0;k<d;++k){
				if(t[i+1]<a[k]||b[k]<t[i+1])
					continue;
				dp[i+1][k]=max(dp[i+1][k],dp[i][j]+abs(c[k]-c[j]));
			}
		}
	}

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

	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#define INF (1<<30)
using namespace std;
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int D, N; cin >> D >> N;
	vector<int> T(D), A(N), B(N), C(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];
	vector<vector<pair<int, int>>> dp(D, vector<pair<int, int>>(N, { 0,-1 }));

	int ans = 0;
	for (int i = 0; i < N;i++) {
		if (T[0] >= A[i] && T[0] <= B[i]) {
			dp[0][i] = { 0,C[i] };
		}
	}

	for (int i = 1; i < D;i++) {
		for (int j = 0; j < N;j++) {
			if (T[i] >= A[j] && T[i] <= B[j]) {
				for (int k = 0; k < N;k++) {
					if (dp[i - 1][k].second != -1) {
						if (dp[i][j].first <= dp[i - 1][k].first + abs(C[j] - dp[i - 1][k].second)) {
							dp[i][j].first = dp[i - 1][k].first + abs(C[j] - dp[i - 1][k].second);
							dp[i][j].second = C[j];
						}
					}
				}

			}
		}
	}
	for (int i = 0; i < N;i++) {
		ans = max(ans, dp[D - 1][i].first);
	}
	cout << ans << endl;
}

C++: #include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
#define ll int64_t
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int dp[202][101];
int t[202],a[202],b[202],c[202];

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,d;
    cin>>n>>d;
    REP(i,n) cin>>t[i];
    REP(i,d) cin>>a[i]>>b[i]>>c[i];
    REP(i,n) REP(j,101) dp[i][j] = -INF;
    REP(i,d) if(a[i]<=t[0] && t[0]<= b[i]) dp[0][c[i]]=0;
    REP(i,n-1){
        REP(j,101){
            if(dp[i][j]>=0){
                REP(k,d){
                    if(a[k]<=t[i+1] && t[i+1] <= b[k]) chmax(dp[i+1][c[k]],dp[i][j]+abs(j-c[k]));
                }
            }
        }
    }
    int ans = 0;
    REP(i,101) chmax(ans,dp[n-1][i]);
    cout<<ans<<endl;
}

C++: #include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct hage {
	int MIN, MAX, POINT;
};
hage huku[250];
int day[250];
int n, m;
int memo[250][250];

int check(int now, int num)
{
	if (now == n - 2)
	{
		int f = 0;
		for (int i = 0; i < m; i++)
		{
			if (day[now + 1] > huku[i].MAX || day[now + 1] < huku[i].MIN)continue;////////////////////////////////////
			if (max(huku[num].POINT, huku[i].POINT) - min(huku[num].POINT, huku[i].POINT) > f)f = max(huku[num].POINT, huku[i].POINT) - min(huku[num].POINT, huku[i].POINT);
		}
		return f;
	}
	if (memo[now][num] != -1)return memo[now][num];
	int aho;
	int HJ=0, JK=0;
	for (int i = 0; i < m; i++)
	{
		if (day[now + 1] > huku[i].MAX || day[now + 1] < huku[i].MIN)continue;///////////////////////////////////////////////
		aho = check(now + 1, i);
		if (HJ < aho){
			HJ = aho; JK = i;
		}
	}
	return memo[now][num]=HJ + (max(huku[JK].POINT, huku[num].POINT) - min(huku[JK].POINT, huku[num].POINT));

}

int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> day[i];
	for (int i = 0; i < m; i++)
		cin >> huku[i].MIN >> huku[i].MAX >> huku[i].POINT;
	for (int i = 0; i < 250; i++)
		for (int t = 0; t < 250; t++)
			memo[i][t] = -1;
	int answer = 0;
	if (n == 0){ cout << "0" << endl; return 0; }
	for (int i = 0; i < m; i++)
	{
		if (day[0]>huku[i].MAX || day[0] < huku[i].MIN)continue;////////////////////////////////////////////////
		int a = check(0, i);
		//cout << i << ":" << a << endl;
		if (answer < a){
			answer = a;
		}
	}
	cout << answer << endl;
	return 0;
}

C++: #include<iostream>
using namespace std;
int main(){
  int dp[1001][1001];
  int n,W;
  int v[1000],w[1000];
  int num=0;
  while(cin>> W,W){
    num++;
    cin>> n;
    for(int i=0;i<n+1;i++){
      dp[0][i]=0;
    }

    for(int i=0;i<n;i++){
      char c;
      cin>> v[i]>> c>> w[i];
    }

    for(int i=1;i<=n;i++){
      for(int j=1;j<=W;j++){
	if(j<w[i-1]){
	  dp[i][j]=dp[i-1][j];
	}else{
	  dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
	}
      }
    }

    int mv=0,mw;
    for(int j=0;j<=W;j++){
      if(mv<dp[n][j]){
	mv=dp[n][j];
	mw=j;
      }
    }
    for(int i=0;i<=n;i++){
      for(int j=0;j<=W;j++){
	cout<< dp[i][j];
      }
      cout<< endl<< endl;
    }

    cout<< "Case "<< num<< ":"<< endl;
    cout<< mv<< endl;
    cout<< mw<< endl;
  }
}