Submission #1058804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058804		GuessWhoHas2Cats	Knapsack (NOI18_knapsack)	C++14	73 / 100	128 ms	262144 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int S, n;
    cin >> S >> n;
    vector<int>w(n + 1), v(n + 1), k(n + 1);
    for(int i = 1; i <= n; i ++)
        cin >> w[i] >> v[i] >> k[i];
    vector<vector<int>>dp(n + 1, vector<int>(S + 1, 0));
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= S; j ++)
        {
            dp[i][j] = dp[i - 1][j];
            for(int kk = 1;kk <= k[i] && (j - v[i] * kk >= 0); kk ++)
            {
                dp[i][j] = max(dp[i - 1][j - kk * v[i]] + kk * w[i], dp[i][j]);
            }
        }
    }
    cout << *max_element(dp[n].begin(), dp[n].end());
    return 0;
}
// 有一个TLE了

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27