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<set>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class Phrase {
    public:
    int s,l,p;
    Phrase(int s,int l,int p) {

        this->s = s;
        this->l = l;
        this->p = p;
    }
    Phrase() {
        s=l=p=0;
    }

};

int n;
Phrase phra[400];
int m;
int w[400];
int dp[400];

int main() {

    cin>>n;
    rep(i,n) {
        int s,l,p;
        cin>>s>>l>>p;
        phra[i] = Phrase(s,l,p);
    }
    cin>>m;
    rep(i,m) cin>>w[i];

    rep(i,n) {
        for(int j=phra[i].s;j<=phra[i].l;j++) {
            for(int k=0;k<400;k+=j) {
                dp[k+j] = max(dp[k+j],dp[k]+phra[i].p);
            }
        }
    }

    multiset<int> ans;
    
    rep(i,m) ans.insert(dp[w[i]]);    
    if(ans.find(-1) != ans.end()) {
        cout<<"-1"<<endl;
        return 0;
    }

    multiset<int>::iterator it = ans.begin();
    while(it != ans.end()) {
        cout<<(*it)<<endl;
        it++;
    }




    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vin=vector<int>;
using vll=vector<long long>;
using vvin=vector<vector<int>>;
using vvll=vector<vector<long long>>;
using vstr=vector<string>;
using vvstr=vector<vector<string>>;
using vch=vector<char>;
using vvch=vector<vector<char>>;
using vbo=vector<bool>;
using vvbo=vector<vector<bool>>;
using vpii=vector<pair<int,int>>;
using pqsin=priority_queue<int,vector<int>,greater<int>>;
#define mp make_pair
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep2(i,s,n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define decp(n) cout<<fixed<<setprecision((int)n)
#define _GLIBCXX_DEBUG
//vector<vector<vector<int>>> dp(101, vector<vector<int>>(101, vector<int>(101)));  
int main(){
    int n;cin>>n;
    vin s(n),l(n),p(n);
    rep(i,n)cin>>s[i]>>l[i]>>p[i];
    int m;cin>>m;
    vin w(m);
    rep(i,m)cin>>w[i];
    vvin dp(n+1,vin(400));//各w[i]についてやるとO(1e10)で間に合わないのでとりあえずw[i]の最大値(393)以上までテーブルを作ってそのあと各w[i]に対応する値をO(1)で見つける
    rep(i,n){
        rep(j,400){
            if(j<s[i])dp[i+1][j]=dp[i][j];
            else{
                int Max=-1;
                rep2(k,s[i],min(l[i],j)+1){
                    if(Max<dp[i+1][j-k])Max=dp[i+1][j-k];
                }
                dp[i+1][j]=max(dp[i][j],Max+p[i]);
            }
        }
    }
    vin score(m);
    bool can=true;
    rep(i,m){
        if(dp[n][w[i]]==0){
            can=false;
            break;
        }
        score[i]=dp[n][w[i]];
    }
    if(can)rep(i,m)cout<<score[i]<<endl;
    else cout<<-1<<endl;
}

C++: #include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

class Phrase {
    public:
    int s,l,p;
    Phrase(int s,int l,int p) {

        this->s = s;
        this->l = l;
        this->p = p;
    }
    Phrase() {
        s=l=p=-1;
    }

};

int n;
Phrase phra[400];
int m;
int w[400];
int dp[400];

int main() {

    cin>>n;
    rep(i,n) {
        int s,l,p;
        cin>>s>>l>>p;
        phra[i] = Phrase(s,l,p);
    }
    cin>>m;
    rep(i,m) cin>>w[i];
    rep(i,400) dp[i]=-1;
    dp[0]=0;

    rep(i,n) {
        for(int j=phra[i].s;j<=phra[i].l;j++) {
            for(int k=0;k<400;k+=j) {
                dp[k+j] = max(dp[k+j],dp[k]+phra[i].p);
            }
        }
    }

    vector<int> ans;
    bool flag = false;
    
    rep(i,m) {
        int t = dp[w[i]];
        if(t < 0) flag=true;
        else ans.push_back(t);
    }
    if(flag) {
        cout<<"-1"<<endl;
        return 0;
    }

    rep(i,ans.size()) cout<<ans[i]<<endl;

    return 0;
}

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

using namespace std;

int main()
{
    int N,M,x;
    cin >> N;
    int s[N],l[N],p[N];
    for(int i = 0 ; i < N ; i++){
	cin >> s[i] >> l[i] >> p[i];
    }
    int dp[500] = {0};
    for(int i = 0 ; i < N ; i++){
	for(int j = 0 ; j < 500 ; j++){
	    for(int k = s[i] ; k <= l[i] ; k++){
		if(j + k >= 500) continue;
		dp[j+k] = max(dp[j+k],dp[j]+p[i]);
	    }	
	}
    }

    cin >> M;
    vector<int> res(M);
    bool check = 0;
    for(int i = 0 ; i < M ; i++){
	cin >> x;
	res[i] = dp[x];
	if(res[i] == 0) check = 1;
    }
    if(check){
	cout << -1 << endl;
    }else{
	for(auto v : res){
	    cout << v << endl;
	}
    }	
    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(n);
    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 <iostream>
#include <vector>

using namespace std;

const int MAX_N = 394;
const int MAX_W = 394;

vector<int> v,w;
int ans[MAX_N];
int dp[MAX_W];

int main() {
    int n,s,l,p;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> s >> l >> p;
        for(int wi=s;wi<=l;wi++) {
            w.push_back(wi);
            v.push_back(p);
        }
    }

    for(int i=0;i<w.size();i++) {
        for(int wi=w[i];wi<=MAX_N;wi++) {
            dp[wi] = max(dp[wi], dp[wi-w[i]] + v[i]);
        }
    }

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