Submission #1018401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018401		arkash707	Knapsack (NOI18_knapsack)	C++17	100 / 100	104 ms	6104 KiB

knapsack

#include<iostream>
#include<string>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#include<vector>
#include <map>
#define pii pair<int, int>
using namespace std;
int mod = 1000000007;


int s, n;
const int N = 100001;
vector<long long> c(N, 0);
vector<long long> w(N, 0);
vector<long long> q(N, 0);



long long solve() {

    //if we group the items by weights we know we can have at most 2000 different
    //items, with the sum of same weights as the freq and varying costs for each
    //we should also take the item with the highest cost from a group


    map<int, vector<pii>> weight_map;

    for (int i=1; i<=n; i++) weight_map[w[i]].push_back({c[i], q[i]});
    for (auto& tp: weight_map) sort(tp.second.begin(), tp.second.end(), greater<pii>());





    vector<long long> dp(s+1, -1);
    long long ans = 0;
    dp[0] = 0;

    for (auto const& [weight, data]: weight_map) {
        
        for (int j=s; j>=0; j--) {    
            
            long long cnt = 0;
            long long cost = 0;



            for (pii d: data) {
                if (cnt > j/weight) break;

                for (int k=0; k<d.second; k++) {
                    cnt++;
                    if (j - cnt*weight < 0) break;
                    cost += d.first;
                    if (dp[j-cnt*weight] == -1) continue;
       
                    dp[j] = max(dp[j], dp[j-cnt*weight] + cost);
                }

            }


            ans = max(ans, dp[j]);
        }
    }

    return ans;





}


int main() {

    cin >> s >> n;
    for (int i=1; i<=n; i++) cin >> c[i] >> w[i] >> q[i];
    cout << solve() << "\n";

}

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