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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1e9 + 7/*998244353*/;
const ll INF = 1LL << 60;
ll mod_pow(ll, ll, ll); ll mod_fact(ll, ll); ll mod_inv(ll, ll); ll gcd(ll, ll); ll lcm(ll, ll);
//
int main(){
    int n;
    cin >> n;
    vector<ll> s(n), l(n), p(n);
    for(int i = 0; i < n; i++) cin >> s[i] >> l[i] >> p[i];
    int m;
    cin >> m;
    vector<ll> w(m);
    ll wmx = 0;
    for(int i = 0; i < m; i++) {cin >> w[i]; wmx = max(wmx, w[i]);}
    vector<vector<ll>> dp(n + 1, vector<ll>(wmx + 1, -1));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
        int cs = s[i - 1], cl = l[i - 1], cp = p[i - 1];
        for(int j = 0; j <= wmx; j++){
            dp[i][j] = dp[i - 1][j];
            for(int k = j - cs; k >= 0 && k >= j - cl; k--){
                dp[i][j] = max(dp[i][j], dp[i][k] + cp);
            }
        }
    }
    for(int i = 0; i < m; i++) if(dp[n][w[i]] == -1) {cout << -1 << "\n"; return 0;}
    for(int i = 0; i < m; i++) cout << dp[n][w[i]] << "\n";
}

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

template<class T> inline void chmax(T& a, T b) { if(b > a) a = b; }

int main() {
	cin.tie(false);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;

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

	vector<int> dp(394, -1);
	dp[0] = 0;
	for(int i = 0; i < 394; ++i) {
		if(dp[i] == -1)
			continue;

		for(int j = 0; j < n; ++j)
			for(int k = s[j]; k <= l[j] && i + k < 394; ++k)
				chmax(dp[i + k], dp[i] + p[j]);
	}

	int m;
	cin >> m;

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

		if(dp[w] == -1) {
			cout << -1 << endl;
			return EXIT_SUCCESS;
		}

		ans[i] = dp[w];
	}

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

	return EXIT_SUCCESS;
}

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

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][400];
  memset(dp,-1,sizeof(dp));
  dp[0][0]=0;

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

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

#define MAX (39*39+1)

int max(int a,int b){ return (a>b)?a:b;}

int main(){
 
	int n;
	int s,l,p;
	int m;
	int w;
	int dp[2][MAX];

	cin>>n;

	for(int i=0;i<MAX;i++){
		for(int j=0;j<2;j++){
			dp[j][i]=-1;
		}
	}

	dp[0][0]=0;

	for(int i=0;i<n;i++){
		cin>>s>>l>>p;
		for(int j=s;j<=l;j++){
			for(int k=0;k<MAX-j;k++){
				if(dp[0][k]>=0){
					dp[1][k+j]=max(dp[1][k+j],dp[0][k]+p);
				}
			}
		}
		for(int i=0;i<MAX;i++){
			dp[0][i]=max(dp[0][i],dp[1][i]);
			dp[1][i]=-1;
		}
	}

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

	return 0;
}