Go: ///
// File:  2502.go
// Author: ymiyamoto
//
// Created on Sat Mar 24 00:44:45 2018
//
package main

import (
	"fmt"
)

type phrase struct {
	s, l, p int
}

const melody_len int = 393

var n, m int

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

func main() {
	fmt.Scan(&n)

	phrases := make([]phrase, n)
	max_count := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&phrases[i].s, &phrases[i].l, &phrases[i].p)
		max_count += phrases[i].l
	}

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

	for i := range phrases {
		s := phrases[i].s
		l := phrases[i].l
		p := phrases[i].p
		for j := range dp[i] {
			for k := s; k <= l; k++ {
				if 0 <= j-k {
					dp[i+1][j] = max(dp[i+1][j], max(dp[i][j], dp[i+1][j-k]+p))
				} else {
					dp[i+1][j] = max(dp[i+1][j], dp[i][j])
				}
			}
		}
	}

	fmt.Scan(&m)
	var invalid bool
	var points []int
	for i := 0; i < m; i++ {
		var m int
		fmt.Scan(&m)
		if dp[n][m] == 0 {
			invalid = true
		}
		points = append(points, dp[n][m])
	}

	if invalid {
		fmt.Println(-1)
	} else {
		for _, p := range points {
			fmt.Println(p)
		}
	}
}

C++: #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;
int n, w, dp[50000][393+1];
vector<int>p, len;

int rec(int i, int j){
  if(dp[i][j] >= 0) return dp[i][j];
  int res;
  if(i == p.size() || j == 0) res = 0;
  else if(j < len[i]) res = rec(i + 1, j);
  else  res = max(rec(i + 1, j), rec(i + 1, j - len[i]) + p[i]);

  return dp[i][j] = res;
}

int main(){
  int n, m, s, l, point;
  memset(dp, -1, sizeof(dp));
  scanf("%d", &n);
  rep(i, n){
    scanf("%d%d%d", &s, &l, &point);
    for(int j = s; j <= l; j++){ len.push_back(j); p.push_back(point);}
  }
  scanf("%d", &m);
  vector<int>res;
  rep(i, m){
    scanf("%d", &w);
    res.push_back(rec(0, w));
  }
  bool f = true;
  rep(i, res.size()) if(res[i] == 0) f = false;
  if(f) rep(i, res.size()) printf("%d\n", res[i]);
  else puts("-1");
  return 0;
}

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

int main(){

    int n; cin >> n;
    vector<int> s(n);
    vector<int> l(n);
    vector<int> p(n);
    for(int i = 0; i < n; i++){
        cin >> s[i] >> l[i] >> p[i];
    }

    int m; cin >> m;
    vector<int> w(m);
    for(int i = 0; i < m; i++){
        cin >> w[i];
    }

    vector<int> v(400, 0);

    for(int i = 0; i < n; i++){
        for(int j = s[i]; j <= l[i]; j++){
            v[j] = max(v[j], p[i]);
        }
    }

    int dp[410][410] = {};
    
    dp[0][0] = 0;

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

    vector<int> ans;
    for(int i = 0; i < m; i++){
        if(dp[399][w[i]] == 0){
            cout << -1 << endl;
            return 0;
        }

        ans.push_back(dp[399][w[i]]);
    }

    for(int i = 0; i < m; i++){
        cout << ans[i] << endl;
    }

    return 0;
}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)

int n, m, dp[395];

int main() {
	cin >> n;
	
	memset(dp, -1, sizeof(dp));
	dp[0] = 0;
	
	for_(i,0,n) {
		int s, l, p;
		cin >> s >> l >> p;		
		for_(d,s,l+1) for_(j,0,395) if (j >= d && dp[j-d] >= 0) dp[j] = max(dp[j], dp[j-d] + p);
	}
	
	cin >> m;
	vector< int > ans(m);
	
	for_(i,0,m) {
		int w;
		cin >> w;
		
		ans[i] = dp[w];
		
		if (ans[i] <= 0) {
			cout << -1 << endl;
			return 0;
		}
	}
	
	for_(i,0,m) cout << ans[i] << endl;
}

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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
#define minit(a,b) memset(a,b,sizeof(a))

void maxUpdate(int& a, int b) {
	a = max(a, b);
}

int n, s[555], l[555], p[555], dp[555][555], m;

int main() {
	cin >> n;
	for_(i,0,n) cin >> s[i] >> l[i] >> p[i];
	
	minit(dp, -1);
	dp[0][0] = 0;
	for_(i,0,n) for_(j,0,394) {
		if (dp[i][j] == -1) continue;
		maxUpdate(dp[i+1][j], dp[i][j]);
		
		for_(k,s[i],l[i]+1) {
			int nj = j + k;
			if (nj > 394) break;
			maxUpdate(dp[i+1][nj], dp[i][j] + p[i]);
		}
	}
	
	vector< int > ans;
	bool flag = true;
	
	cin >> m;
	for_(i,0,m) {
		int w;
		cin >> w;
		ans.push_back(dp[n][w]);
		if (ans[i] <= 0) flag = false;
	}
	
	if (flag) {
		for_(i,0,m) cout << ans[i] << endl;
	} else {
		cout << -1 << endl;
	}
}

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

int n;
int lo[400], hi[400], score[400];
int dp[1000];

void calcDP(){
  memset(dp, -1, sizeof(dp));
  dp[0] = 0;

  for(int i = 0; i < 393; i++){
    if(dp[i] == -1) continue;

    for(int j = 0; j < n; j++){
      for(int k = lo[j]; k <= hi[j]; k++){
        if(i + k > 393) continue;
        dp[i + k] = max(dp[i + k], dp[i] + score[j]);
      }
    }
  }
}

int main(){
  while(cin >> n){
    for(int i = 0; i < n; i++){
      cin >> lo[i] >> hi[i] >> score[i];
    }

    calcDP();

    vector<int> v;
    int m;
    cin >> m;

    for(int i = 0; i < m; i++){
      int len;
      cin >> len;
      if(dp[len] != -1){
        v.push_back(dp[len]);
      }
    }

    if(v.size() != m){
      cout << -1 << endl;
      continue;
    }

    for(int i = 0; i < m; i++){
      cout << v[i] << endl;
    }
  }
}

C++: #include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <memory.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    vector<int> S(N), L(N), P(N);
    for (int n = 0; n < N; ++n) {
        cin >> S[n] >> L[n] >> P[n];
    }
    int M;
    cin >> M;
    vector<int> W(M);
    for (int m = 0; m < M; ++m) {
        cin >> W[m];
    }
    
    int DP[395][395];
    memset(DP, 0, sizeof(DP));
    for (int n = 1; n <= N; ++n) {
        for (int w = 0; w <= 395; ++w) {
            DP[n][w] = DP[n-1][w];
            if (w >= S[n-1]) {
                for (int k = max(0, w-L[n-1]); k <= w-S[n-1]; ++k) {
                    DP[n][w] = max(DP[n][w], DP[n-1][k] + P[n-1]);
                    DP[n][w] = max(DP[n][w], DP[n][k] + P[n-1]);
                }
            }
        }
    }
    
    for (int m = 0; m < M; ++m) {
        if (DP[N][W[m]] == 0) {
            cout << -1 << endl;
            return 0;
        }
    }
    
    for (int m = 0; m < M; ++m) {
        cout << DP[N][W[m]] << endl;
    }
    

    return 0;
}

C++: #include <iostream>
#include <cstring>

using namespace std;

int main(){
  int n;
  cin>> n;
  int d[400],u[400],s[400];
  for(int i=0;i<n;i++) cin>>d[i]>>u[i]>>s[i];
  
  int dp[400]={};

  for(int i=0;i<n;i++)
    for(int k=u[i];k>=d[i];k--)
      for(int j=399;j>=0;j--)
	if(j+k<400 && dp[j]!=-1) dp[j+k] = max(dp[j+k],dp[j]+s[i]);
      
  int q,flg=0,m[400];
  cin>> q;
  for(int i=0;i<q;i++){
    cin >> m[i];
    if(dp[m[i]] == -1) flg= 1;
  }
  if(flg) cout << -1<<endl;
  else 
    for(int i=0;i<q;i++) cout << dp[m[i]]<<endl;
  return 0;
}