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 <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 i=0; i*S[0]<=MAX; 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<=MAX; j++) {
			dp[i][j] = max(dp[i][j], dp[i-1][j]);
			for (int l=0; l*S[i]<=MAX; 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 <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// typedef
typedef long long ll;

// container util
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

// repetition
#define FOR(i,m,n) for(ll i = ((ll) m); i < ((ll) n); ++i)
#define REP(i,n) FOR(i,0,n)

struct Phrase {
    int s;
    int l;
    int p;
};

int main() {
    int n; cin >> n;
    Phrase* ph = new Phrase[n];
    REP(i, n) cin >> ph[i].s >> ph[i].l >> ph[i].p;
    const int MAX = 393;
    int s[MAX+1];
    REP(m, MAX+1) s[m] = 0;
    REP(k, n) {
        FOR(m, ph[k].s, MAX+1) {
            int val = s[m];
            FOR(t, ph[k].s, min((ll)ph[k].l, m)+1) {
                val = max(val, s[m-t]+ph[k].p);
            }
            s[m] = val;
        }
    }
    int m; cin >> m;
    int *w = new int[m];
    bool error = false;
    REP(i, m) {
        cin >> w[i];
        error |= s[w[i]] == 0;
    }
    if (error) {
        cout << -1 << endl;
    } else {
        REP(i, m) cout << s[w[i]] << endl;
    }
    return 0;
}
/*
VOCAL ANDROID
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502

dp[k][m] = k番目までのフレーズのみを使った時に長さmのメロディが得られる最大のスコア
dp[k][m] = max_{s..l}{0..} {dp[k-1][m - nt]+ns}
         = max_{s..l} max(dp[k-1][m], max_{1..} {dp[k-1][m - nt]+ns})
         = max_{s..l} max(dp[k-1][m], max_{0..} {dp[k-1][m - t - nt]+ns} + s)
         = max_{s..l} max((dp[k-1][m], dp[k][m-t]+s)
*/

C++: #include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#define X first
#define Y second
using namespace std;
const int MAX = 394; 
int dp[394][394];

void DP(int amount, int sq, int v){
	for(int j = 1; j < MAX; j++){
		if(amount > j) dp[sq][j] = dp[sq-1][j]<dp[sq][j]?dp[sq][j]:dp[sq-1][j];
		else{
			if(!dp[sq-1][j-amount]) continue;
			int tmp = dp[sq-1][j]<dp[sq-1][j-amount]+v ? dp[sq-1][j-amount]+v : dp[sq-1][j];
			dp[sq][j] = tmp<dp[sq][j] ? dp[sq][j] : tmp;
		}
	}
}

int main(){
	int n;
	cin >> n;
	for(int i = 0; i <= n; i++) fill(dp[i], dp[i]+MAX, 0);
	int sq = 0;
	while(n--){
		sq++;
		int up, down, v;
		cin >> down >> up >> v;
		while(down <= MAX){
			if(up>=MAX) up = MAX-1;
			for(int i = down; i <= up; i++){
				int tmp = dp[sq-1][i]<v?v:dp[sq-1][i];
				dp[sq][i] = dp[sq][i]<v?v:dp[sq][i];
			}
			for(int i = 0; i < 2; i++){
				if(i) DP(up, sq, v);
				else DP(down, sq, v);
			}
			up += up;
			down += down;
		}
	}
	int m;
	cin >> m;
	while(m--){
		int input;
		cin >> input;
		if(dp[sq][input]) cout << dp[sq][input] << endl;
		else cout << "-1" << endl;
	}
	return 0;
}

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];
  memset(dp,-1,sizeof(dp));
  dp[0][0]=0;

  for(int i=1;i<=n;i++){
    deque<int> deq;    
    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-1][j-k]>=0)dp[i][j]=max(dp[i][j],dp[i-1][j-k]+c[i]);
      }
      /*
      int key=j-a[i];
      if(key>=0&&dp[i-1][key]>=0){
	while(!deq.empty()&&dp[i-1][deq.back()]<=dp[i-1][key])deq.pop_back();
	deq.push_back(key);
      }
      
      while(!deq.empty()&&deq.front()<j-b[i])deq.pop_front();
      if(!deq.empty())dp[i][j]=max(dp[i][j],dp[i-1][deq.front()]+c[i]);
      */
    }
  }

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

C++: #include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
  int n, m, s[393], l[393], p[393], w;
  vector< int > dp( 394, -1); //dp[i]:i長のメロディを作るための最大値
  dp[0] = 0;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> s[i] >> l[i] >> p[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j <= 393; j++){
      if(dp[j] == -1) continue;
      for(int k = s[i]; k <= l[i] && j + k < 394; k++){
        dp[j + k] = max( dp[j + k], dp[j] + p[i]);
      }
    }
  }
  cin >> m;
  vector< int > ret(m);
  bool flag = true;
  for(int i = 0; i < m && flag; i++){
    cin >> w;
    ret[i] = dp[w];
    flag &= ret[i] != -1;
  }
  if(flag){
    for(int i = 0; i < m; i++){
      cout << ret[i] << endl;
    }
  }else{
    cout << -1 << endl;
  }
  return 0;
}