洛谷P 1782トラベラーのリュック[多重リュック]

タイトルの説明
Sさんはどんな問題も多項式の時間で解決できると信じて、自分で旅行業者になるつもりです.出発する前に、彼はいくつかの品物を購入した.これらの品物はn種類あり,i種類目の体積はVi,価値はWi,Di件である.彼のリュックサックの体積はCです.どのように装ってできるだけ多くの収益を得ることができますか?大神として、彼は簡単にこの問題を解決した.
しかし、彼が出発する前に、彼はまた珍しい品物を受け取った.これらの品物はm件を共有し、i件目の価値Yiと分配された体積Xiの関係は:Yi=ai*Xi^2+bi*Xi+ciである.これはいいことですが、Sさんはどうやって処理したのか分かりません.そこで、彼はスーパー神様(つまりあなた)を見つけました.この問題を解決してください.
にゅうしゅつりょくけいしき
入力形式:
 
第1行の3つの数n,m,Cは、問題に記載されているように.
以下のn行は、各行に3つの数Vi、Wi、Diがあり、問題に記載されているようにする.
以下のm行は、各行に3つの数ai,bi,ciがあり、問題に記載されているようにする.
 
出力フォーマット:
 
1行のみが最大の価値です.
 
入出力サンプル
サンプル#1を入力:

2 1 10
1 2 3
3 4 1
-1 8 -16

出力サンプル#1:

10

説明
【データ範囲】
100%のデータに対して,1≦n≦10000,1≦m≦5,1≦C≦10000,
1≤Wi,Vi,Di≤1000,-1000≤ai,bi,ci≤1000.
【様式解釈】
前の2つの品物はすべて選んで、最後の奇貨は4の体積に分けて、収益は2*3+4*1+-1*16+8*4+-16=10です.
時限3 s
 
 
マルチバックパックバイナリ分割
mは小さくて、爆枚でいいです.

#include
#include
#include
#include
#include
using namespace std;
const int N=1e4+5,INF=1e9;
int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,v,w,c,C,m,a,b;
int f[N];
inline void zp(int v,int w){
    for(int j=C;j>=v;j--) f[j]=max(f[j],f[j-v]+w);
}
inline void cp(int v,int w){
    for(int j=v;j<=C;j++) f[j]=max(f[j],f[j-v]+w);
}
inline void mp(int v,int w,int c){
    if(c*v>C){cp(v,w);return;}
    int k=1;
    while(k<c){
        zp(v*k,w*k);
        c-=k;
        k*=2;
    }
    zp(v*c,w*c);
}
int main(){
    n=read();m=read();C=read();
    for(int i=1;i<=n;i++){
        v=read();w=read();c=read();
        mp(v,w,c);
    }
    for(int i=1;i<=m;i++){
        a=read(),b=read(),c=read();
        for(int j=C;j>=0;j--)
            for(int k=0;k<=j;k++) f[j]=max(f[j],f[j-k]+(a*k+b)*k+c);
    }
    printf("%d",f[C]);
}