问题标题: 酷町堂：7005

#include<iostream>
#include<cstring>
using namespace std;
int t,m,n,w[1001],a[1001],b[1001],f[1001][2001];
int main(){
    cin>>t;
    while(t--){
        memset(w,0,sizeof(w));
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        cin>>m>>n;
        for(int i=1;i<=n;i++){
            cin>>w[i]>>a[i]>>b[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=w[i];j<=m;j++){
                f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+a[i]*w[i]+b[i]);
            }
        }
        cout<<f[n][m]/2<<endl;
    }
}

WA0分