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>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)x
#define lp(i,n) for(int i=0;i<(n);++i)

#define REPA(i,n) for(int i=1;i<(n);++i)
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define PIPII pair<int, pair<int, int> >
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
#define BIT(x) (1 << (x))
using namespace std;
int ans[400];

int main(){
  lp(i,400){
    ans[i]=-1;
  }
  ans[0]=0;
  int n;
  cin>>n;
  int maxi=0;
  lp(i,n){
    int s,l,p;
    cin>>s>>l>>p;
    for(int i=0;i<=399;i++){
      if(ans[i]!=-1){
	for(int j=i+s;j<=min(399,l+i);j++){
	  ans[j]=max(ans[j],ans[i]+p);
	}
      }
    }/*
    lp(i,20){
      cout<<ans[i]<<" ";
    }
    cout<<endl;*/
  }
  int q;
  cin>>q;
  vector<int> v;
  int check=0;
  lp(i,q){
    int hoge;
    cin>>hoge;
    v.push_back(ans[hoge]);
    if(ans[hoge]==-1){
      check=1;
    }
  }
  if(check==1) cout<<-1<<endl;
  else{
    lp(i,q){
      cout<<v[i]<<endl;
    }
  }
  
  return 0;
}

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,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);
            }
        }
    }

    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 <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);
	int M = -1;
	for (int i=0; i<m; i++) {
		cin >> W[i];
		M = max(M, 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 i=0; i*S[0]<=M; i++)
		for (int j=i*S[0]; j<=i*S[0]+SUB[0]; j++)
			dp[0][j] = max(dp[0][j], i*P[0]);
	
	for (int i=1; i<n; i++) {
		for (int j=0; j<=M; j++) {
			for (int l=0; l*S[i]<=M; l++) {
				for (int k=l*S[i]; k<l*S[i]+SUB[i]; k++) {
					dp[i][j+k] = max(max(dp[i][j+k], dp[i-1][j+k]), dp[i-1][j]+l*P[i]);
				}
			}
		}
	}

	vector<int> point(m);
	bool flag = false;
	for (int i=0; i<m; i++) {
		point[i] = dp[n][W[i]];
		for (int j=0; j<n; j++)
			point[i] = max(point[i], dp[j][W[i]]);
		if (!point[i]) {
			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<bits/stdc++.h>
using namespace std;
int main(){
    int n,i,j,k,m,w;cin >> n;
    int f[n][3];vector<int> ans;
    for(i=0;i<n;i++) cin >> f[i][0] >> f[i][1] >> f[i][2];
    cin >> m;
    int dp[394] = {};
    for(i=1;i<=393;i++) dp[i] = -1;
    for(i=0;i<n;i++){
        for(j=f[i][0];j<=f[i][1];j++){
            for(k=j;k<=393;k++){
                if(dp[k-j] != -1) dp[k] = max(dp[k],dp[k-j]+f[i][2]);
            }
        }
    }
    while(cin >> w){
        if(dp[w]==-1){
            cout << -1 << endl;return 0;
        }
        ans.push_back(dp[w]);
    }
    for(auto x:ans) cout << x << endl;
}

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

using namespace std;

#define FOREACH(it,c) for(__typeof(c.begin()) it = c.begin(); it != c.end(); ++it)
#define TIMES(i,n) for(int i = 0; i < (n); ++i)

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    while(cin >> N) {
        vector<int> phrases(394, 0);
        int maxlen = 0;
        TIMES(i, N) {
            int S, L, P;
            cin >> S >> L >> P;
            for(int l = S; l <= L; ++l) {
                phrases[l] = max(phrases[l], P);
            }
            maxlen = max(maxlen, L);
        }
        int M;
        cin >> M;
        vector<int> WS(M);
        TIMES(i, M) {
            cin >> WS[i];
        }
        vector<int> ans;
        FOREACH(it, WS) {
            const int W = *it;
            vector<int> dp(W+1, 0);
            TIMES(pos, W) {
                TIMES(len, maxlen+1) {
                    const int next = pos+len;
                    if(next > W) break;
                    dp[next] = max(dp[next], dp[pos]+phrases[len]);
                }
            }
            if(dp[W] == 0) {
                ans.clear();
                ans.push_back(-1);
                break;
            } else {
                ans.push_back(dp[W]);
            }
        }
        FOREACH(it, ans) {
            cout << *it << endl;
        }
    }
    return 0;
}