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 <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  int n;
  scanf("%d",&n);
  std::vector<int > s(n), l(n), p(n);
  for (int i=0; i<n; i++){
    scanf("%d",&s[i]);
    scanf("%d",&l[i]);
    scanf("%d",&p[i]);
  }
  int m;
  scanf("%d",&m);
  std::vector<int > w(m);
  for (int i=0; i<m; i++){
    scanf("%d",&w[i]);
  }
  std::vector<std::vector<int > > dp(n, std::vector<int > (394, 0));

  // i=0 case
  for (int j=0; j<=393; j++){
    if (j<s[0]){
      dp[0][j] = 0;
    } else {
      for (int k=s[0]; k<=l[0]; k++){
        dp[0][j] = std::max(dp[0][std::max(j-k,0)]+p[0], dp[0][j]);
      }
    }
  }
  
  // i>0 case
  for (int i=1; i<n; i++){
    for (int j=0; j<=393; j++){
      if (j<s[i]){
        dp[i][j] = dp[i-1][j];
      } else {
        for (int k=s[i]; k<=l[i]; k++){
          dp[i][j] = std::max(dp[i][std::max(j-k,0)]+p[i], dp[i][j]);
        }
        dp[i][j] = std::max(dp[i-1][j], dp[i][j]);
      }
    }
  }
  
  // answer
  bool ng = false;
  for (int i=0; i<m; i++){
    if (dp[n-1][w[i]]==0){
      ng = true;
    }
  }
  
  if (ng) {
    printf("-1\n");
  } else {
    for (int i=0; i<m; i++){
      printf("%d\n",dp[n-1][w[i]]);
    }
  }
  return 0;
}

C++: #include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>
   
using namespace std;
   
 
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define rforeach(it, c) for (__typeof__((c).rbegin()) it=(c).rbegin(); it != (c).rend(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))
#define COPY(dest, src) memcpy(dest, src, sizeof(dest))
#define ten(n) ((long long)(1e##n))
#define bin(n) (1ull << (n))
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define revrep(i, n) for (int i = (n); i >= 0; --i)
#define pb push_back

template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }

template <class T> void uniq(T& c) { sort(c.begin(), c.end()); c.erase(unique(c.begin(), c.end()), c.end()); }
 
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
  
template <class T, class U> ostream& operator<<(ostream& os, pair<T, U>& p) { os << "( " << p.first << ", " << p.second << " )"; return os; }
  
template <class T> void print(T a, int n, const string& deli = " ", int br = 1) { for (int i = 0; i < n; ++i) { cout << a[i]; if (i + 1 != n) cout << deli; } while (br--) cout << endl; }
template <class T> void print(const T& c, const string& deli = " ", int br = 1) { foreach (it, c) { cout << *it; if (++it != c.end()) cout << deli;--it; } while (br--) cout << endl; }
template <class T> void print2d(T a, int w, int h, int width = -1, int br = 1) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) {    if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
   
template <class T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
template <class T> void input(T* a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }

void fix_pre(int n) { cout.setf(ios::fixed, ios::floatfield); cout.precision(10); }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
#define trace(x) (cout << #x << ": " << (x) << endl)
 
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }


typedef long long ll;
typedef pair<int, int> pint;
 
// y(v): v>^<  y(^): ^>v<
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };

const double PI = acos(-1.0);


int main()
{
    int n, s[555], l[555], p[555];
    cin >> n;
    rep(i, n)
        cin >> s[i] >> l[i] >> p[i];

    const int inf = ten(8);
    int dp[555][800];
    erep(i, n) erep(j, 393)
        dp[i][j] = -inf;
    dp[0][0] = 0;
    rep(i, n) erep(j, 393)
    {
        // not use
        chmax(dp[i + 1][j], dp[i][j]);

        // use
        for (int len = s[i]; len <= l[i]; ++len)
            chmax(dp[i + 1][j + len], dp[i + 1][j] + p[i]);
    }

    vector<int> sol;
    int m;
    cin >> m;
    rep(i, m)
    {
        int w;
        cin >> w;
        if (dp[n][w] < 0)
        {
            cout << -1 << endl;
            return 0;
        }
        sol.pb(dp[n][w]);
    }
    rep(i, m)
        cout << sol[i] << endl;
}

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
  int n, m, s[393], l[393], p[393], w;
  vector< int > dp( 394, -1); //dp[i]:i長のメロディを作るための最大値
  dp[0] = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s[i] >> l[i] >> p[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 394; j++){
      if(dp[j] == -1) continue;
      for(int k = s[i]; k <= l[i] && j + k < 394; k++){
        dp[j + k] = max( dp[j + k], dp[j] + p[i]);
      }
    }
  }
  cin >> m;
  while(m--){
    cin >> w;
    cout << dp[w] << endl;
  }
  return 0;
}