Submission #1106346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106346		GuessWhoHas2Cats	Knapsack (NOI18_knapsack)	C++14	100 / 100	75 ms	35144 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define vPII vector<PII>
#define ll long long
#define vl vector<ll>
#define vvl vector<vl>
#define pb push_back
#define all(x) (x).begin(), (x).end()
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int W, n; 
    cin >> W >>  n;
    map<int, vPII>group_by_weight;
    for(int i = 0; i < n ; i ++)
    {
        int val, we, amt;
        cin >> val >> we >> amt;
        if(we <= W && amt > 0)
            group_by_weight[we].pb({val, amt});
    }
    vvl dp(group_by_weight.size() + 1, vl(W + 1, 0));
    dp[0][0] = 0;
    for(int at = 1; auto &[w, items] : group_by_weight)
    {
       sort(all(items), std::greater<PII>());
       for(int j = 0; j <= W; j ++)
       {
            dp[at][j] = dp[at - 1][j];
            int copies = 0, type_at = 0, curr_used = 0;
            ll profit = 0;
            // 和第2层循环一起的时间复杂度是 O(W * logW)
            while((copies + 1) * w <= j && (type_at < items.size()))
            {
                copies ++;
                profit += (ll) items[type_at].first;
                // if(dp[at - 1][j - copies * w] != INT_MIN)
                // {
                    dp[at][j] = max(dp[at][j], dp[at - 1][j - copies * w] + profit);
                // }
                curr_used ++;
                if(curr_used == items[type_at].second)
                {
                    curr_used = 0;
                    type_at ++;
                }
            }
       }
        at ++;
    }
    cout << dp[group_by_weight.size()][W];
    // cout << *std::max_element(dp.back().begin(), dp.back().end()) << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:26:21: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   26 |     for(int at = 1; auto &[w, items] : group_by_weight)
      |                     ^~~~
knapsack.cpp:26:27: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(int at = 1; auto &[w, items] : group_by_weight)
      |                           ^
knapsack.cpp:35:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |             while((copies + 1) * w <= j && (type_at < items.size()))
      |                                             ~~~~~~~~^~~~~~~~~~~~~~

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