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++: // 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;
	vi res;
	rep(i, m){
		int w;
		cin >> w;
		if (dp[w] < 0){
			res.clear();
			res.eb(-1);
			break;
		}
		res.eb(dp[w]);
	}

	for (int x : res) cout << x << endl;
}

C++: #include <iostream>
#include <vector>
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 <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,395) {
		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 <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,395) {
		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 - k > 400 ) break;
			if (nj < k) maxUpdate(dp[i+1][nj], dp[i][nj]);
			else dp[i+1][nj] = max(dp[i][nj], dp[i+1][nj-k] + 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;
	}
}