Submission #845037

#	Time	Username	Problem	Language	Result	Execution time	Memory
845037		taimoitapcode1	Knapsack (NOI18_knapsack)	C++17	100 / 100	108 ms	35152 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long

ll oo = 1e18 + 7, res = 0;

int limit, n;

vector<pair<int, int>> weight[2005];

ll dp[2005][2005];

int main(){
    cin >> limit >> n;
    for (int i = 1; i <= n; i++){
        int weigh, value, cnt;
        cin >> value >> weigh >> cnt;
        weight[weigh].push_back({value, cnt});
    }

    for (int i = 1; i <= limit; i++) sort(weight[i].begin(), weight[i].end(), greater<pair<int, int>>());
    
    for (int i = 0; i <= limit; i++){
        for (int cost = 0; cost <= limit; cost++) dp[i][cost] = -oo;
    }

    dp[0][0] = 0;

    for (int i = 1; i <= limit; i++){
       
        
        for (int cost = 0; cost <= limit; cost++){
            int index = 0;
            int cnt = 1;
            int typee = 0;
            ll hihi = 0;

            dp[i][cost] = dp[i - 1][cost];
            
            while(cnt * i <= cost && typee < weight[i].size()){
                hihi += weight[i][typee].fi;
                if(dp[i - 1][cost - cnt * i] != oo) dp[i][cost] = max(dp[i][cost], dp[i - 1][cost - cnt * i] + hihi);
                res = max(res, dp[i][cost]);
                index++;
                cnt++;
                if(index == weight[i][typee].se){
                    index = 0;
                    typee++;
                }
            }
        }

    }

    cout << res;
    
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:42:44: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(cnt * i <= cost && typee < weight[i].size()){
      |                                      ~~~~~~^~~~~~~~~~~~~~~~~~

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