Submission #1268933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268933		tkvinhtruongquang	Knapsack (NOI18_knapsack)	C++17	100 / 100	59 ms	17480 KiB

knapsack

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

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define clz __builtin_clz
#define popcount __builtin_popcount
#define lb(x) lower_bound(x)
#define ub(x) upper_bound(x)
#define loop(i, j, n, k) for(int i = j; i <= n; i += k)
#define fast ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)

template <typename T>
inline void print(T x) { cerr << x << endl; }
template <typename T>
inline void print(vector <T> x) { cerr << '['; loop(i, 0, sz(x) - 2, 1) cerr << x[i] << ", "; cerr << x.back() << ']' << endl; }
template <typename T>
inline bool maximize(T &a, const T &b) { return a < b ? (a = b) : 0; }
template <typename T>
inline bool minimize(T &a, const T &b) { return a > b ? (a = b) : 0; }

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pss = pair<string, string>;
using vll = vector<ll>;
using pll = pair<ll, ll>;

#define debug(x) cerr << #x << " = "; print(x)

mt19937 rng(chrono :: steady_clock :: now().time_since_epoch().count());
template <typename T>
inline int rand_range(T l, T r) { return uniform_int_distribution<T> (l, r)(rng); }

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
    freopen("error.txt", "w", stderr);
}

struct dt {
    int v, w, k;
};

const int INF = 1e9;

int main() {
    // setIO("task");

    fast;
    int S, N; cin >> S >> N;

    // stored weights and their best 
    map<int, vector<pii>> mp;

    loop(i, 0, N - 1, 1) {
        int v, w, k; cin >> v >> w >> k;
        mp[w].pb({v, k});
    }

    // dp[i][j] denotes the maximum values obtained by buying the first i
    // types of items with weight j
    vector<vi> dp(sz(mp) + 5, vi(S + 5, -1));

    // base case : haven't bought anything yet
    dp[0][0] = 0;
    
    // This is for iterating over all types of items
    int cur_type = 1;

    for(auto &[w, items] : mp) {
        sort(all(items), greater<pii>());

        loop(j, 0, S, 1) {
            // we paste over the last dp
            dp[cur_type][j] = dp[cur_type - 1][j];

            int copies = 0;
            int cur_item = 0;
            int profit = 0;
            int cur_used = 0;
            
            while(cur_item < items.size() && (copies + 1) * w <= j) {
                copies ++;
                cur_used ++;
                profit += items[cur_item].fi;
                
                if(dp[cur_type - 1][j - copies * w] != -1) { // it was not possible to get to this weight
                    dp[cur_type][j] = max(dp[cur_type][j], dp[cur_type - 1][j - copies * w] + profit);
                }

                // this item is out of stock, we need to get to the next item
                if(cur_used == items[cur_item].se) {
                    cur_used = 0;
                    cur_item ++;
                }
            } 
        }

        cur_type ++;
    }

    cout << *max_element(all(dp[sz(mp)])) << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen("error.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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