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

import (
	"fmt"
)

var n, m int

type phrase struct {
	s, l, p 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, max_count+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 <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int dp[3939];
 
int main()
{
    int n;
     
    scanf("%d", &n);
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for (int i = 0; i < n; i++){
        int low, up, val;
        scanf("%d %d %d", &low, &up, &val);
         
        for (int d = low; d <= up; d++)
            for (int v = 0; v + d <= 393; v++)
                if (~dp[v]) dp[v + d] = max(dp[v] + val, dp[v + d]);
    }
     
    int m;
    scanf("%d", &m);
     
    int ans[3939];
    for (int i = 0; i < m; i++){
        int s;
        scanf("%d", &s);
        if (~dp[s]) ans[i] = dp[s];
        else return (!printf("-1\n"));
    }
     
    for (int i = 0; i < m; i++) printf("%d\n", ans[i]);
     
    return (0);
}

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

int score;
int n, m;
int w;
int s[400], l[400], p[400];
void dp(int num, int melodyLength){
	if(melodyLength == w){
		score = max(score, num);
	}

	for(int i=0; i < n; i++){
		for(int j=s[i]; j <= l[i]; j++){
			if(melodyLength + j <= w){
				dp(num + p[i], melodyLength + j);
			}
		}
	}
}

int main(){
	cin >> n;
	for(int i=0; i < n; i++){
		cin >> s[i] >> l[i] >> p[i];
	}
	cin >> m;
	for(int j=0; j < m; j++){
		score = 0;
		cin >> w;
		dp(score, 0);

		cout << score << endl;
	}


}

C++: #include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
using ll = long long;
using P = pair<int, int>;
using namespace std;

template<class T> void vin(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }
}

int n, m;
int s[400], l[400], p[400];
int w[400];

int dp[400][401];

int main() {
    cin >> n;
    rep(i, n) {
        cin >> s[i] >> l[i] >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= 400; ++j) {
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            for (int k=s[i]; k<=l[i]; ++k) {
                if (j >= k) {
                    dp[i+1][j]=max({dp[i][j], dp[i+1][j], dp[i+1][j-k]+p[i]});
                }
                else dp[i+1][j] = max(dp[i][j], dp[i+1][j]);
            }
        }
    }
    cin >> m;
    bool ok = true;
    rep(i, m) {
        cin >> w[i];
        if (dp[n][w[i]] == 0) {
            ok = false;
        }
    }
    if (!ok) {
        cout << -1 << endl;
        return 0;
    }
    rep(i, m) {
        cout << dp[n][w[i]] << endl;
    }
    return 0;
}

C++: // template {{{

#include <bits/stdc++.h>

// #define int long long

#define GET_MACRO(a, b, c, d, NAME, ...) NAME
#define REP2(i, n) REP3(i, 0, n)
#define REP3(i, a, b) REP4(i, a, b, 1)
#define REP4(i, a, b, s) for (int i = (a); i < (int)(b); i += s)
#define RREP2(i, n) RREP3(i, 0, n)
#define RREP3(i, a, b) for (int i = (b) - 1; i >= (int)(a); i--)

#define rep(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define rrep(...) GET_MACRO(__VA_ARGS__,, RREP3, RREP2)(__VA_ARGS__)
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define all(c) std::begin(c), std::end(c)
#define mp std::make_pair
#define mt std::make_tuple
#define fi first
#define se second
#define popcnt __builtin_popcountll

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = std::vector<int>;
using vvi = std::vector<vi>;

template<typename T>
using maxpq = std::priority_queue<T, std::vector<T>, std::less<T>>;

template<typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

const int MOD = 1e9 + 7;
const int INF = 1e9 + 10;
const ll LLINF = 1e18 + 10;

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

template<typename T>
inline T sq(T x){ return x * x; }

template<typename T, typename U>
inline bool chmax(T &x, U y){ if (x >= y) return false; x = y; return true; }

template<typename T, typename U>
inline bool chmin(T &x, U y){ if (x <= y) return false; x = y; return true; }

template<typename T>
inline void sort(T &c){ std::sort(std::begin(c), std::end(c)); }

template<typename T>
inline void reverse(T &c){ std::reverse(std::begin(c), std::end(c)); }

template<typename T>
inline void unique(T &c){ std::sort(std::begin(c), std::end(c)); c.erase(std::unique(all(c)), std::end(c)); }

using namespace std;

// }}}

int main()
{
	int dp[400];
	fill_n(dp, 400, -INF);
	dp[0] = 0;

	int n;
	cin >> n;
	rep(i, n){
		int a, b, c;
		cin >> a >> b >> c;
		rep(j, a, b + 1){
			rep(k, 400 - j){
				chmax(dp[k + j], dp[k] + c);
			}
		}
	}

	int m;
	cin >> m;
	rep(i, m){
		int w;
		cin >> w;
		cout << (dp[w] == -INF ? -1 : dp[w]) << endl;
	}
}

C++: #include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
const int LEN = 400;

int main() {
  int N; cin >>N;
  vector<int> v(LEN, -1);
  v[0] = 0;
  REP(z, N){
    int S, L, P; cin >>S >>L >>P;
    REP(i, LEN){
      if(v[i] == -1) continue;
      FOR(t, i + S, min(LEN, i + L + 1)) v[t] = max(v[t], v[i] + P);
    }
  }
  int M; cin >>M;
  vector<int> ws(M);
  bool f = 0;
  REP(i, M){
    int w; cin >>w;
    if(v[w] == -1) f = 1;
    ws[i] = w;
  }
  if(f) cout <<-1 <<endl;
  else REP(i, M) cout <<v[ws[i]] <<endl;
  return 0;
}