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;

#define rep(i,n) for(int i=0;i<(int)(n);i++)
void sort2array(double *a,long *b,long n){
    for(int i=0;i<n;i++){
        b[i]=i;
    }
    sort(b,b+n,[a](long i,long j)->bool {return a[i]<a[j];} );
}
//bを何回足せばaを超えるか
int wtover(int a,int b){
    if(a%b>0)return (a/b)+1;
    else return a/b;
}
const int INF=100000001,ID_MAX=20;
int bi_e[ID_MAX]={0};
//2進数表示したときの最高桁
int bi_max(long n){
    int m=0;
    for(m;pow(2,m)<=n;m++);m=m-1;
    return m;
}
//bi_eに二進数表示したやつを代入
void bi_exs(long n){
    rep(i,ID_MAX){
        bi_e[i]=0;
    }
    if(n<pow(2,ID_MAX)){
        int m=bi_max(n);
        long l;
        for(m;m>-1;m--){
            l=pow(2,m);
            bi_e[m]=n/l;
            n=n%l;
        }
    }
}
//x^n mod m (nが負の時は０)
long myPow(long x, long n, long m){
  if(n<0)return 0;
  if(n == 0)
    return 1;
  if(n % 2 == 0)
    return myPow(x * x % m, n / 2, m);
  else
    return x * myPow(x, n - 1, m) % m;
}

const int N_MAX=394;
int n,s[N_MAX],l[N_MAX],p[N_MAX],m,w[N_MAX],dp[N_MAX][N_MAX]={0},res[N_MAX];

int main(){
    int i;
    //入力
    cin>>n;
    rep(i,n){
        cin>>s[i+1]>>l[i+1]>>p[i+1];
    }
    cin>>m;
    rep(i,m){
        cin>>w[i];
    }
    //処理
    bool tof=false;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=N_MAX-1;j++){
            int res=dp[i-1][j];
            if(j>=s[i]){
                for(int k=s[i];k<=min(l[i],j);k++){
                    res=max(res,dp[i][j-k]+p[i]);
                }
            }
            dp[i][j]=res;
        }
    }
    //出力
    rep(i,m){
        res[i]=dp[n][w[i]];
        if(res[i]==0){
            cout<<"-1"<<endl;
            return 0;
        }
    }
    rep(i,m){
        cout<<res[i]<<endl;
    }
}

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

int main(){
    int n;
    cin >> n;

    int point[n];
    vector<pair<int, int> > phase(n);

    for(int i = 0; i < n; i++){
        int s, l, p;
        cin >> s >> l >> p;
        point[i] = p;
        phase[i].first = s;
        phase[i].second = l;
    }

    int x;
    cin >> x;
    int length[x];

    for(int i = 0; i < x; i++){
        cin >> length[i];
    }

    int dp[400];
    for(int m = 0; m <= 400; m++){
        dp[m] = -1;
    }
    dp[0] = 0;

    for(int m = 0; m <= 400; m++){
        for(int i = 0; i < n; i++){
            for(int l = phase[i].first; l <= phase[i].second; l++){
                if(m - l < 0){
                    continue;
                }
                dp[m] = max(dp[m], dp[m-l]+point[i]);
            }
        }
    }


    for(int i = 0; i < x; i++){
        if(dp[length[i]] == -1){
            printf("-1\n");
            return 0;
        }
        
    }

    for(int i = 0; i < x; i++){
        printf("%d\n", dp[length[i]]);
        
    }

    

    return 0;
}

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

#define loop(i,a,b) for(int i=a; i<b; i++)
#define rep(i,n) loop(i,0,n)

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

int m,n;

int dp[800];

void disp(int i, int j, int arr[]){
    for(int x=i; x<=j; x++)
        cout<<arr[x]<<" ";
    cout<<endl;
}

int main(){
    memset(dp,0,sizeof(dp));
    cin>>n;
    rep(i,n) cin>>s[i]>>l[i]>>p[i];
    rep(i,394){
        rep(j,n){
            loop(len,s[j],l[j]+1) dp[i+len]=max(dp[i]+p[j],dp[i+len]);
        }
        //disp(0,20,dp);
    }
    cin>>m;
    int ans[393];
    rep(i,m){
        int t;cin>>t;
        if(dp[t]==0){
            cout<<-1<<endl;
            return 0;
        } else ans[i]=dp[t];
    }
    rep(i,m)cout<<ans[i]<<endl;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define i_7 (ll)(1E9+7)
#define i_5 (ll)(1E9+5)
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    else return c+i_7;
}
typedef pair<int,int> i_i;
typedef pair<ll,ll> l_l;
ll inf=(ll)1E12;//10^12
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll * pos,ll val){*pos=max(*pos,val);}//Max(&dp[i][j],dp[i-1][j]);
void Min(ll * pos,ll val){*pos=min(*pos,val);}
//const long double EPS=1E-8;
////////////////////////////////////////


int main(){
    //ios::sync_with_stdio(false);cin.tie(0);
    
    int n;cin>>n;
    int s[n][3];rep(i,0,n-1)rep(j,0,2)cin>>s[i][j];
    rep(i,0,n-1){
        if(s[i][1]>=2*s[i][0])s[i][1]=2*s[i][0]-1;
    }
    int N=400;
    ll dp[N];fill(dp,dp+N,0);
    rep(i,0,n-1){
        rep(j,0,N-1){
            rep(k,s[i][0],s[i][1])
            if(j-k>=0)Max(&dp[j],dp[j-k]+s[i][2]);
        }
    }
    //rep(i,0,10)cout<<dp[i]<<" ";
    int m;cin>>m;
    vector<ll>ans;
    rep(i,0,m-1){
        int k;cin>>k;
        if(!dp[k]){cout<<-1<<endl;return 0;}
        ans.pb(dp[k]);
    }
    for(auto x:ans)cout<<x<<endl;
    
    return 0;
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>

using namespace std;

int main() {
	int n;

	cin >> n;

	vector< int > s, l, p;

	for(int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		s.push_back(a);
		l.push_back(b);
		p.push_back(c);
	}

	vector< int > dp(394, 0);
	for(int i = 0; i < n; i++) {
		dp[s[i]] = p[i];
		dp[l[i]] = p[i];
	}

	int m;
	cin >> m;
	vector< int > w;

	for(int i = 0; i < m; i++) {
		int tmp;
		cin >> tmp;
		w.push_back(tmp);
	}

	for(int i = 0; i < m; i++) {
		bool flag = true;
		for(int j = 1; j <= 100; j++) {
			for(int k = 0; k < n; k++) {
				dp[j + s[k]] = max(dp[j + s[k]], dp[j] + p[k]);
				dp[j + l[k]] = max(dp[j + l[k]], dp[j] + p[k]);
				if(j + s[k] > w[i]) {
					flag = false;
					break;
				}
			}
			if(!flag) {
				break;
			}
		}
	}

	bool flag = true;
	for(int i = 0; i < m; i++) {
		if(dp[w[i]] == 0) {
			flag = false;
		}
	}

	for(int i = 0; i < m; i++) {
		if(flag) {
			cout << dp[w[i]] << endl;
		} else {
			cout << "-1" << endl;
			break;
		}
	}
}

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

int l[400],p[400];
int dp[400][400];
int main(){
	int n;scanf("%d",&n);
	rep(i,n)scanf("%d%*d%d",&l[i],&p[i]);
	int m;scanf("%d",&m);
	vector<int>v;
	rep(i,m){
		int w;scanf("%d",&w);
		rep(j,n)rep(k,w+1){
			dp[j+1][k]=max(dp[j+1][k],dp[j][k]);
			if(k+l[j]<=w)dp[j+1][k+l[j]]=max(dp[j+1][k+l[j]],dp[j][k]+p[j]);
		}
		if(dp[n][w]==0){puts("-1");return 0;}
		v.push_back(dp[n][w]);
	}
	for(int i:v)printf("%d\n",i);
}