AOJ2502

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502

ボカロかな？（）
解法：制限なしナップサック同様のDP　計算量謎
ナップサック問題の重さに幅があるというだけ
数の制約が小さいのでこれでOK

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(){
    int n,m;
    cin >> n;
    int s,l,p;
    int w[400]={0,};
    for(int i=0;i<n;i++){
        cin >> s >> l >> p;
        for(int j=s;j<=l;j++){
            for(int k=0;k+j<=399;k++){
                w[k+j]=max(w[k+j],w[k]+p);
            }
        }
    }
    cin >> m;
    int d[m];
    bool ans = true;
    for(int i=0;i<m;i++){
        cin >> d[i];
        if(!w[d[i]])ans=false;
    }
    if(!ans)cout << -1 << endl;
    else{
        for(int i=0;i<m;i++){
            cout << w[d[i]] << endl;
        }
    }
}