Submission #1139675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139675		HUYHDUVE	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	17480 KiB

knapsack

//  ^------^
// ( '(oo)' )
// (  u  u  )

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define ff first
#define sc second
#define IN "A.IN"
#define OUT "A.OUT"
#define cerr if(0) cerr

int const MOD = 1e9 + 7;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    if(fopen(IN, "r")){
        freopen(IN, "r", stdin);
        freopen(OUT, "w", stdout);
        freopen("CERR.txt", "w", stderr);
    }

    int n, s; cin >> s >> n;
    vector<vector<pii>> stuff(s + 1);

    vector<int> cnt(s + 1, 0);
    for(int i = 0; i < n; i++){
        int w, val, k;
        cin >> val >> w >> k;
        cnt[w] += k;
        cnt[w] = min(s, cnt[w]);
        stuff[w].push_back({val, k});
    }




    vector<vector<int>> val_weight(s + 1, vector<int> (s + 1, 0));
    for(int w = 1; w <= s; w++){
        sort(stuff[w].rbegin(), stuff[w].rend());
        int pi = 0;
        for(int j = 1; j <= cnt[w]; j++){
            val_weight[w][j] = stuff[w][pi].ff;
            val_weight[w][j] += val_weight[w][j - 1];
            stuff[w][pi].sc --;
            if(stuff[w][pi].sc == 0) pi ++;
        }
    }



    vector<ll> max_p(s + 1, LLONG_MIN/2);

    max_p[0] = 0;
    for(int w = 1; w <= s; w++){
        for(int i = s; i >= w; i--){
            for(int j = 1; j <= cnt[w]; j++){
                if(w*j > i) break;
                if(max_p[i - w*j] != LLONG_MIN/2) {
                    max_p[i] = max(max_p[i], max_p[i - w*j] + val_weight[w][j]);
                }
            }
        }
    }

    ll ans = 0;
    for(int i = 0; i <= s; i++){
        ans = max(ans, max_p[i]);
    }

    cout << ans;

    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen("CERR.txt", "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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