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 <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

int dp[400];
int main() {
    int N; cin >> N;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i=0; i<N; i++) {
        int s, l, p; cin >> s >> l >> p;
        for(int j=0; j<400; j++) {
            for(int k=s; k<=l; k++) {
                if(j - k < 0) continue;
                if(dp[j - k] < 0) continue;
                dp[j] = max(dp[j], dp[j - k] + p);
            }
        }
    }
    
    int M; cin >> M;
    bool no_answer = false;

    vector<int> rec(M);
    for(int i=0; i<M; i++) {
        int v; cin >> v;
        rec[i] = v;
        no_answer |= (dp[v] < 0); 
    }

    if(no_answer) cout << -1 << endl;
    else {
      for(int i=0; i<M; i++) {
        cout << dp[ rec[i] ] << endl;
      }
    }
    return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int dp[400][400];


	
int main (){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	//input
	int n,m;
	cin >> n;
	vector<int> S(n);
	vector<int> G(n);
	vector<int> P(n);
	for(int i=0;i<n;i++){
		cin >> S[i] >> G[i] >> P[i];
	}
	cin >> m;
	vector<int> L(m);
	for(int i=0;i<m;i++)cin >> L[i];
	memset(dp,-1,sizeof(dp));

	//algorithm
	for(int i=1;i<=n;i++){
		for(int j=1;j<395;j++){
			int maxx=0;
			if(j<S[i-1]) dp[i][j]=dp[i-1][j];
			else {
				for(int k=S[i-1];k<=G[i-1];k++){
					if(j<k)break;
					if(dp[i][j-k]==-1)maxx=max(maxx,dp[i][j-k]+P[i-1]+1);
					else maxx=max(maxx,dp[i][j-k]+P[i-1]);
				}
				dp[i][j]=max(maxx,dp[i-1][j]);
			}
		}
	}

	//output
	for(int i=0;i<m;i++) {
		if(dp[n][L[i]]==-1){cout << -1 << endl;return 0;}
	}

	
	for(int i=0;i<m;i++) {
		cout << dp[n][L[i]] << endl;
	}
	
	
}

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

#define MAX (393*393+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;
}

C++: 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef unsigned long long ULL;
template<class T> inline bool amax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool amin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> ostream& operator << (ostream &os, const vector<T> &v) { os << "["; for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); it++) { os << (it != v.begin() ? ", " : "") << *it; } os << "]"; return os; }
template<class T> ostream& operator << (ostream &os, const set<T> &s) { os << "["; for (typename set<T>::const_iterator it = s.begin(); it != s.end(); it++) { os << (it != s.begin() ? ", " : "") << *it; } os << "]"; return os; }
template<class Key, class Val> ostream& operator << (ostream &os, const map<Key, Val> &m) { os << "{"; for (typename map<Key, Val>::const_iterator it = m.begin(); it != m.end(); it++) { os << (it != m.begin() ? ", " : "") << it->first << ":" << it->second; } os << "}"; return os; }
template<class T, class S> ostream& operator << (ostream &os, const pair<T, S> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T> istream& operator >> (istream &is, vector<T> &v) { for (size_t i = 0; i < v.size(); i++) is >> v[i]; return is; }
template <class Target, class Source> inline Target lexical_cast (const Source &s) { Target t; stringstream ss; ss << s; ss >> t; return t; }

//> v < ^ (clock wise)
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
const int INFI = 1<<28;
const long long int INFL = 1LL<<60;
const double INFD = 1e+300;
const float INFF = 1e+100;
const double EPS = 1e-8;
const long long int MOD = 1000000007;

int solve ();
int main () {
    cout.setf(ios::fixed); cout.precision(10);
    ios_base::sync_with_stdio(false);
    solve();
    return 0;
}

int solve () {
    int n;
    cin >> n;
    int s, l, p;
    int score[1000];
    for (int i = 0; i < 1000; i++) score[i] = -INFI;
    score[0] = 0;
    for (int i = 0; i < n; i++) {
        cin >> s >> l >> p;
        for (int k = 0; k < 1000; k++) {
            for (int j = s; j <= l; j++) {
                if (k+j < 1000) score[k+j] = max(score[k+j], score[k]+p);
            }
        }
    }

    int m;
    cin >> m;
    vector<int> ans(m);
    bool ng = false;
    for (int i = 0; i < m; i++) {
        int w;
        cin >> w;
        ans[i] = score[w];
        ng |= score[w]<0;
    }
    if (ng) cout << -1 << endl;
    else {
        for (int i = 0; i < m; i++) cout << ans[i] << endl;
    }

    return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;
int dp[2][395][395];
int main(){
  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];
  }
  fill_n(**dp,2*395*395,-1);
  dp[0][0][0]=0;
  for(int i=0;i<n;i++){
    int ii=i%2;
    int ni=(i+1)%2;
    for(int j=0;j<395;j++)
      for(int k=j;k<395;k++)
	dp[ni][j][k]=-1;

    for(int j=0;j<395;j++){
      for(int k=j;k<395;k++){
	if(dp[ii][j][k]==-1)continue;
	dp[ni][j][k]=max(dp[ni][j][k],dp[ii][j][k]);
	int nj=min(394,j+s[i]);
	int nk=min(394,k+l[i]);
	dp[ni][nj][nk]=max(dp[ni][nj][nk],dp[ii][j][k]+p[i]);
	dp[ii][nj][nk]=max(dp[ii][nj][nk],dp[ii][j][k]+p[i]);
      }
    }
  }
  int m;
  cin>>m;
  vector<int> ans;
  int f=0;
  for(int i=0;i<m;i++){
    int w;
    cin>>w;
    int ma=-1;
    for(int j=0;j<395;j++)
      for(int k=j;k<395;k++){
	if(j<=w&&w<=k)ma=max(dp[n%2][j][k],ma);
      }
    if(ma==-1)f=1;
    ans.push_back(ma);
  }
  if(f)cout<<-1<<endl;
  else for(int i=0;i<m;i++)cout<<ans[i]<<endl;
  return 0;
}

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

#define MAX 400

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

	cin>>n;

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

	dp[0]=0;

	for(int i=0;i<n;i++){
		cin>>s>>l>>p;
		f=true;
		while(f){
			f=false;
			for(int j=s;j<=l;j++){
				for(int k=0;k<=MAX-j;k++){
					if(dp[k]>=0){
						if(dp[k+j]<dp[k]+p){
							dp[k+j]=dp[k]+p;
							f=true;
						}
					}
				}
			}
		}
	}

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

	return 0;
}