Submission #1094991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094991		vjudge1	Knapsack (NOI18_knapsack)	C++17	100 / 100	37 ms	3676 KiB

knapsack

/** DRAFT
  placeholder
**/

#include "bits/stdc++.h"

using namespace std;

#define MULTI_TEST 0
#define IN "TASK.INP"
#define OUT "TASK.OUT"
// #define cerr if (false) cerr

using lint = long long;

constexpr int MOD = int(1e9) + 7; // 998244353;
constexpr int MAX = 0x3f3f3f3f;
constexpr lint LMAX = lint(1e18) + 5;
int test_case = 1;

#define all(a) begin(a), end(a)

void solve() {
  // cerr << "Case #" << test_case++ << ":\n";
  int goal, n;
  cin >> goal >> n;

  constexpr int W = 2000 + 5;
  /// items[w] are items with weight w, each item is (value, count)
  vector<array<int, 2>> items[W];
  
  for (int i = 0, v, w, c; i < n; i++) {
    cin >> v >> w >> c;
    items[w].push_back({v, c});
  }

  vector<lint> dp(W);

  for (int weight = 1; weight <= goal; weight++) {
    if (items[weight].empty()) {
      continue;
    }
    sort(all(items[weight]), greater<array<int, 2>>());
    int i = 0;
    for (int rep = 0; rep < goal / weight; rep++) {
      for (int w = goal; w >= weight; w--) {
        dp[w] = max(dp[w], dp[w - weight] + items[weight][i][0]);
      }
      items[weight][i][1]--;
      if (items[weight][i][1] == 0) {
        i++;
      }
      if (i == (int) items[weight].size()) {
        break;
      }
    }
  }

  lint ans = *max_element(all(dp));
  cout << ans;
}

signed main() {
  if (fopen("iii.txt", "r")) {
    freopen("iii.txt", "r", stdin);
    freopen("ooo.txt", "w", stdout);
    freopen("eee.txt", "w", stderr);
  }
  if (fopen(IN, "r")) {
    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);
  }
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cerr << __cplusplus << '\n';

  int t = 1;
  if (MULTI_TEST)
    cin >> t;
  while (t --> 0) {
    solve();
    cout << '\n';
  }
  cerr << '\n' << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";

  return 0;
}

/**
--------------------------------------------------
X                     INPUT                      X
--------------------------------------------------

--------------------------------------------------
X                     OUTPUT                     X
--------------------------------------------------

**/

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen("iii.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen("ooo.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen("eee.txt", "w", stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:70:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     freopen(IN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:71:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |     freopen(OUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~

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