WA10pts求调

部分背包

#include<bits/stdc++.h>
using namespace std;
vector<int> v[100], w[100];
int n, m, dp[32768];
int main(){
    cin >> m >> n;
    for(int i = 1; i <= n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(z != 0){
            for(int j : v[z]) v[z].push_back(x*y+j);
            for(int j : w[z]) w[z].push_back(x+j);
        }
        else{
            v[i].push_back(x*y);
            w[i].push_back(x);
        }
    }
    for(int i = 1; i <= n; i++)
        for(int j = m; j >= 0; j--)
            for(int k = 0; k < v[i].size(); k++)
                if(j >= w[i][k]) dp[j] = max(dp[j], dp[j-w[i][k]]+v[i][k]);
    cout << dp[m];
    return 0;
}