Submission #709313

#	Time	Username	Problem	Language	Result	Execution time	Memory
709313		nima_aryan	Knapsack (NOI18_knapsack)	C++17	17 / 100	3 ms	3412 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template<class Fun>
class y_combinator_result {
   Fun fun_;
public:
   template<class T>
   explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
 
   template<class ...Args>
   decltype(auto) operator()(Args &&...args) {
      return fun_(std::ref(*this), std::forward<Args>(args)...);
   }
};
 
template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
   return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int S, N;
   cin >> S >> N;
   vector<int> V(N + 1), W(N + 1), K(N + 1);
   for (int i = 1; i <= N; ++i) {
      cin >> V[i] >> W[i] >> K[i];
   }
   const int maxb = 18;
   vector<pair<int, int>> items;
   for (int i = 1; i <= N; ++i) {
      for (int bit = 0; bit <= maxb; ++bit) {
         if (K[i] >> bit & 1) {
            items.emplace_back(i, 1 << bit);
         }
      }
   }
   const i64 inf = 1e18;
   const int num = (int) items.size();
   vector dp(num + 1, vector<i64>(S + 1, -inf));
   dp[0][0] = 0;
   for (int i = 1; i <= num; ++i) {
      auto [idx, cnt] = items.at(i - 1);
      for (int sum = 0; sum <= S; ++sum) {
         dp[i][sum] = dp[i - 1][sum];
         i64 opt = (i64) sum - (i64) cnt * W[idx];
         if (opt >= 0) {
            dp[i][sum] = max(dp[i][sum], dp[i - 1][opt] + (i64) cnt * V[idx]);
         }
      }
   }
   i64 ans = 0;
   for (int sum = 0; sum <= S; ++sum) {
      ans = max(ans, dp.back().at(sum));
   }
   cout << ans << '\n';
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

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