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 main(int argc, char *argv[]){
  int n, m;
  cin >> n;
  vector<int> s(n), l(n), p(n);
  vector<vector<int> > dp(n + 1, vector<int>(394, -1));
  for (int i = 0; i < n; i++) {
    cin >> s[i] >> l[i] >> p[i];
  }
  dp[0][0] = 0;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 394; j++) {
      for (int k = s[i]; k <= l[i]; k++) {
        if(j < k){
          dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);        
        }else{
          if(dp[i + 1][j - k] == -1)continue;
          dp[i + 1][j] = max(dp[i + 1][j],
                             max(dp[i][j],
                                 dp[i + 1][j - k] + p[i]));
        }
      }
    }
  }
  cin >> m;
  int query;
  vector<int> ans;
  for (int i = 0; i < m; i++) {
    cin >> query;
    ans.push_back(dp[n][query]);
    if(ans.back() == -1){
      std::cout << -1 << std::endl;
      return 0;
    }
  }
  for (int i: ans) {
    std::cout << i << std::endl;
  }
  return 0;
}

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

int main() {
  int n; cin >> n;
  int s[n], l[n], p[n];
  rep(i, n) {
    int a, b, c; cin >> a >> b >> c;
    s[i] = a; l[i] = b; p[i] = c;
  }
  
  int dp[n][395]; memset(dp, -1, sizeof(dp));
  rep(i, n) {
    rep(j, 395) {
      int ii = max(i-1, 0);
      int x = s[i], y = l[i];
      if (j < x) {
        dp[i][j] = dp[ii][j];
      }
      else if (j >= x && j <= y) {
        dp[i][j] = max(dp[ii][j], p[i]);
        for (int k = x; k <= j; k++) {
          if (dp[i][j-k] != -1) {
            dp[i][j] = max(dp[i][j], dp[i][j-k] + p[i]);
          }
        }
      }
      else {
        dp[i][j] = dp[ii][j];
        for (int k = x; k <= y; k++) {
          if (dp[i][j-k] != -1) {
            dp[i][j] = max(dp[i][j], dp[i][j-k] + p[i]);
          }
        }
      }
    }
  }
  
  int m; cin >> m;
  vector<int> point(m);
  bool finish = false;
  rep(i, m) {
    int w; cin >> w;
    if (dp[n-1][w] == -1) {
      finish = true;
      break;
    }
    point[i] = dp[n-1][w];
  }
  if (finish) {
    cout << -1 << endl;
    return 0;
  }
  else {
    rep(i, m) {
      cout << point[i] << endl;
    }
  }
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define ALL(c) c.begin(),c.end()
#define RALL(c) c.rbegin(),c.rend()
#define REP(type,i,n) for(type i=0;i<(n);++i)
#define MP(a,b) make_pair((a),(b))
#define F_ first
#define S_ second

typedef long long int lli;
typedef pair<int,int> Pi;

const int INF=100000000;
const long long int INF_=1000000000000000000;

int main(){
	int N;
	cin >> N;
	vector<int> m(394);
	REP(int,i,N){
		int s,l,p;
		cin >> s >> l >> p;
		for(int j=s; j<=l; ++j) m[j]=max(m[j],p);
	}
	REP(int,i,394){
		REP(int,j,i+1){
			m[i]=max(m[i],m[i-j]+m[j]);
		}
	}
	//REP(int,i,9) cout << m[i] << ' ';
	cout << endl;
	int M;
	cin >> M;
	vector<int> ans;
	bool flag=true;
	REP(int,i,M){
		int w;
		cin >> w;
		if(m[w]==0) flag=false;
		else ans.push_back(m[w]);
	}
	if(!flag) cout << -1 << endl;
	else REP(int,i,ans.size()) cout << ans[i] << endl;
	return 0;
}

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

using namespace std;

#define range(i, a, b) for(int i = (a); i < (b); ++i)
#define rep(i, n) range(i, 0, n)
#define all(a) (a).begin(), (a).end()
#define s first.first
#define l first.second 
#define p second

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 394;

int main(){
	int n; cin >> n;
	vector< pair<pii, int> > f(n);

	rep(i, n) cin >> f[i].s >> f[i].l >> f[i].p;

	vi dp(N);
	fill(all(dp), -1);
	dp[0] = 0;

	rep(i, n){
		range(j, f[i].s, f[i].l + 1){
			rep(k, N){
				if(dp[k] != -1 && k + j < 400){
					dp[k + j] = max(dp[k + j], dp[k] + f[i].p);
				}
			}
		}
	}

	int m; cin >> m;
	vi res(m);

	rep(i, m){
		int w; cin >> w;

		res[i] = dp[w];
	}

	if(find(all(res), -1) != res.end()) cout << -1 << endl;
	else rep(i, m) cout << res[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<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define mp make_pair
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef pair<int,pii> pip;
typedef vector<pip>vip	;
const double PI=acos(-1);
const double EPS=1e-8;
const int inf=1e8;
int main(){
	int n;
	cin>>n;
	vvi in(n,vi(3));
	rep(i,n)rep(j,3)cin>>in[i][j];
	vi dp(400);
	rep(i,n)rep(j,400)loop(k,in[i][0],in[i][1]+1)if(j+k<400){
		dp[j+k]=max(dp[j+k],dp[j]+in[i][2]);
	}
	int q;
	cin>>q;
	vi out(q);
	bool h=true;
	rep(i,q){
		int a;cin>>a;
		out[i]=dp[a];
		if(out[i]==0)h=false;
	}
	if(!h)cout<<-1<<endl;
	else rep(i,q)cout<<out[i]<<endl;
}