Submission #633428

#	Time	Username	Problem	Language	Result	Execution time	Memory
633428		tourist_2022	Knapsack (NOI18_knapsack)	C++17	100 / 100	99 ms	33152 KiB

knapsack

#include<bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);
#define Created ios_base::sync_with_stdio(0);
#define By cin.tie(0);
#define Sofar cout.tie(0);
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define rsz resize
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
const long long int MOD=1e9+7, OO=0x3f3f3f3f;
const long long int  LOO=0x3f3f3f3f3f3f3f3f;
const long double EPS=1e-8;

int main(){
    Created By Sofar
    int limit , types_amount;
    cin >> limit >> types_amount;
    map< int , vector<pi> > weights;
    for(int i = 0 ; i < types_amount ; i++)
    {
        int value , its_weight , amount;
        cin >> value >> its_weight >> amount ;
        if(amount > 0 && its_weight <= limit)
        {
            weights[its_weight].pb({value,amount});
        }
    }
    vector<vector<ll>>dp(
        weights.size()+1 , vector<ll>(limit+1,INT32_MIN)
        );
    int k = 1;
    dp[0][0] = 1;
    for(auto &[w,items] : weights)
    {
        sort(items.begin(), items.end(), greater<pair<int, int>>());
        for(int i = 0 ; i <= limit ; i++)
        {
            dp[k][i] = dp[k-1][i];
            int copies = 1;
            int type_at = 0;
            int curr_used = 0;
            long long profit = 0;
            while ((copies) * w <= i && type_at < items.size()) {
                profit += items[type_at].first;
                    dp[k][i] = std::max(
                            dp[k][i],
                            dp[k - 1][i - copies * w] + profit
                    );
                copies++;
                curr_used++;
                if (curr_used == items[type_at].second) {
                    curr_used = 0;
                    type_at++;
                }

            }

        }
        k++;
    }
    cout << *std::max_element(dp.back().begin(), dp.back().end())-1 << endl;


    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:50:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             while ((copies) * w <= i && type_at < items.size()) {
      |                                         ~~~~~~~~^~~~~~~~~~~~~~

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