Go: ///
// File:  2502.go
// Author: ymiyamoto
//
// Created on Sat Mar 24 00:44:45 2018
//
package main

import (
	"fmt"
)

var n, m int

type phrase struct {
	s, l, p 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, max_count+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;
int n,a[394],b[394],c[394];
int dp[394][394];

int main(){
  cin>>n;
  for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
  for(int i=0;i<394;i++)for(int j=0;j<394;j++)dp[i][j]=-1;

  dp[0][0]=0;
  for(int i=1;i<=n;i++){
    for(int j=0;j<=393;j++){      
      dp[i][j]=dp[i-1][j];      
      for(int k=a[i];k<=b[i];k++){
	if(j-k>=0&&dp[i][j-k]>=0)dp[i][j]=max(dp[i][j],dp[i][j-k]+c[i]);
      }
    }
  }

  int q,Q;
  cin>>Q;
  vector<int> ans;
  while(Q--){
    cin>>q;
    ans.push_back(dp[n][q]);
    if(dp[n][q]==-1){
      cout<<-1<<endl;
      return 0;
    }
  }
  for(int i=0;i<ans.size();i++)cout<<ans[i]<<endl;
  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define Rep(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define Repr(i, b, e) for(int (i) = (b) - 1; (i) >= (e); --(i))
#define Print(x) cout << (x) << endl 
#define Min2(a, b) ((a) < (b)) ? (a) : (b)
#define Max2(a, b) ((a) > (b)) ? (a) : (b)

typedef long long ll;

using namespace std;

#define L 394
int N, M;
int s[L], l[L], p[L], w[L];
int dp[L];

void solve(){
    Rep(i, 0, L) dp[i] = 0;
    Rep(i, 0, N){
        Rep(j, 0, L){
            Rep(k, s[i], l[i] + 1){
                if(j >= k) dp[j] = Max2(dp[j - k] + p[i], dp[j]);
            }
        }
    }
}

int main(){
    cin >> N;
    Rep(i, 0, N) cin >> s[i] >> l[i] >> p[i];
    cin >> M;
    Rep(i, 0, M) cin >> w[i];
    solve();
    Rep(i, 0, M){
        if((w[i] = dp[w[i]]) == 0){
            Print("-1");
            return 0;
        }
    }
    Rep(i, 0, M) Print(w[i]);
    return 0;
}

C++: #include <bits/stdc++.h>
#define ALL(A) (A).begin(), (A).end()
#define ll long long
#define rep(i, n) for (int i = 0; i < (n); i++)

using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll mod = 1e9 + 7;
const ll INF = -1 * ((1LL << 63) + 1);
const int inf = -1 * ((1 << 31) + 1);

int l,r,s,x;

int dp[400];

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int n,m;
    cin >> n;
    vector<int> v,w;
    rep(_,n){
        cin >> l >> r >> s;
        for(int i=l;i<=r;i++){
            w.push_back(i);
            v.push_back(s);
        }
    }
    rep(i,400){
        rep(j,w.size()){
            if(i>=w[j])chmax(dp[i],dp[i-w[j]]+v[j]);
        }
    }
    cin >> m;
    vector<int> ans;
    rep(i,m){
        cin >> x;
        ans.push_back(dp[x]==0?-1:dp[x]);
        if(dp[x]==0){
            cout << -1 << endl;
            return 0;
        }
    }
    for(auto x:ans)cout << x << endl;
}

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

using namespace std;

int dp[400];

int main(int argc, char const* argv[])
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
			int s, l, p;
			cin >> s >> l >> p;
			for(int j = s; j < 394; j++){
					for(int k = s; k < l; k++){
							if(j - k < 0)continue;
							dp[j] = max(dp[j], dp[j - k] + p);
					}
			}
	}

	int m;
	cin >> m;
	vector<int> vec;
	for(int i = 0; i < m; i++){
			int w;
			cin >> w;
			if(dp[w] != 0){
					vec.push_back(dp[w]);
			}else{
					cout << -1 << endl;
					return 0;
			}
	}
	for(auto itr = vec.begin(); itr != vec.end(); ++itr){
			cout << *itr << endl;
	}
	return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<set>
#include<utility>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef pair<ll,ii> P;
typedef unsigned long long int ull;
const int MOD=1e9+7;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
const int MAXN=100000;
const int MAXE=100000;
const int MAXV=10000;
const ll INF=2e9;

int main(){
    int n;cin>>n;
    int s[n],t[n],p[n];
    for(int i=0;i<n;i++) cin>>s[i]>>t[i]>>p[i];
    int dp[n+1][394];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=393;j++){
            dp[i][j]=-1;
        }
    }
    dp[0][0]=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=393;j++){
            dp[i+1][j]=dp[i][j];
            for(int k=s[i];k<=p[i];k++){
                if(j>=k&&dp[i+1][j-k]!=-1) dp[i+1][j]=max(dp[i+1][j],dp[i+1][j-k]+p[i]);
            }
        }
    }
    int m;cin>>m;
    int ans[m];
    for(int i=0;i<m;i++){
        int w;cin>>w;
        ans[i]=dp[n][w];
        if(ans[i]==-1){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

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

using namespace std;

int MAX = 393;

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

	vector<int> S(n), L(n), P(n);//, SUB(n);
	for (int i=0; i<n; i++) {
		cin >> S[i] >> L[i] >> P[i];
		//SUB[i] = L[i]-S[i];
	}

	int m;
	cin >> m;

	vector<int> W(m);
	for (int i=0; i<m; i++)
		cin >> W[i];

	int **dp = new int*[MAX+10];
	for (int i=0; i<MAX+10; i++) {
		dp[i] = new int[3*MAX];
		for (int j=0; j<3*MAX; j++)
			dp[i][j] = 0;
	}

	dp[0][0] = 0;
	for (int j=S[0]; j<=L[0]; j++)
		dp[0][j] = max(dp[0][j], P[0]);
	
	for (int i=1; i<n; i++) {
		for (int j=0; j<=MAX; j++) {
			dp[i][j] = dp[i-1][j];
			if (j>=S[i])
				for (int k=S[i]; k<=L[i]; k++)
					if (j-S[i]>=0) dp[i][j] = max(dp[i][j], dp[i][j-k]+P[i]);
		}
	}

	vector<int> point(m);
	bool flag = false;
	for (int i=0; i<m; i++) {
		point[i] = dp[n-1][W[i]];
		if (point[i]==0) {
			flag = true;
			break;
		}
	}
	
	if (flag) cout << -1 << endl;
	else {
		for (int i=0; i<m; i++)
			cout << point[i] << endl;
	}

	for (int i=0; i<MAX+10; i++)
		delete [] dp[i];
	delete [] dp;

	return 0;
}

C++: #include <iostream>
#include <cstring>
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]={};
  memset(dp,-1,sizeof(dp));
  dp[0]=0;

  for(int i=0;i<n;i++)
    for(int j=399;j>=0;j--)
      for(int k=d[i];k<=u[i];k++)
	if(j+k<400 && dp[j]!=-1) dp[j+k] = max(dp[j+k],dp[j]+s[i]);
      

  
int q;
  cin>> q;
  while(q--){
    int m;
    cin>> m;
    cout << dp[m]<<endl;
  }
  return 0;
}