Submission #1101202

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101202		Plot_Twist	Knapsack (NOI18_knapsack)	C++17	0 / 100	1076 ms	168068 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define int long long

bool comp(pair<int,int>&p1,pair<int,int>&p2) {
    if(p1.first==p2.first) return p1.second > p2.second;
    else return p1.first > p2.first;
} 

signed main () {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n,limit;
    cin>>n>>limit;

    // ------Grouping by weight----------
    map<int,vector<pair<int,int>>>mp;
    for(int i = 0; i < n; i++) {
        int val, wt, am;
        cin>>val>>wt>>am;
        mp[wt].push_back({val,am});
    }
    // ----------------------------------


    // ------Initializing DP ------------
    int wtcnt = mp.size();
    int dp[wtcnt+1][limit+1];
    for(int i = 0; i<= wtcnt; i++) 
        for(int j = 0; j<=limit;j++) dp[i][j] = INT32_MIN;
    // ----------------------------------

    int level = 1;
    dp[0][0] = 0;
    for(auto &[wt,arr] : mp) {
        sort(arr.begin(),arr.end(),comp);
        int sz= arr.size();
        for(int i = 0; i<=limit; i++) {
            dp[level][i] = dp[level-1][i];   // NOT TAKE
            int idx = 0;
            int value = 0;
            int amount_taken = 0;
            int curr_item_used = 0;
            while((amount_taken+1)*wt <= i && idx < sz) {
                amount_taken++;
                value+= arr[idx].first;
                if(dp[level-1][i-amount_taken*wt]!= INT32_MIN) {
                    dp[level][i] = max(dp[level][i], value + dp[level-1][i-amount_taken*wt]);
                }
                curr_item_used++;
                if(curr_item_used==arr[idx].second) {
                    idx++;
                    curr_item_used=0;
                }
            }
        }
        level++;
    }
    int ans = -1;
    for(int i = 0; i<= limit; i++) ans = max(ans, dp[wtcnt][i]);
    cout<<ans<<endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:13:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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