Submission #1209762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209762		manthan0x23	Knapsack (NOI18_knapsack)	C++20	73 / 100	287 ms	327680 KiB

knapsack

#include <bits/stdc++.h>
// manthan's code
using namespace std;
#define tc                                                                     \
  int t;                                                                       \
  cin >> t;                                                                    \
  while (t--)
#define each(x, v) for (auto &x : v)
#define min_heap(T) priority_queue<T, vector<T>, greater<T>>
#define max_heap(T) priority_queue<T>
#define hash_map(T1, T2) unordered_map<T1, T2, custom_hash>
#define hash_set(T) unordered_set<T>
#define loop(i, a, b, step) for (int i = (a); i < (b); i += step)
#define asc(v) sort((v).begin(), (v).end())
#define dsc(v) sort((v).rbegin(), (v).rend())

using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vll = vector<ll>;
using vi = vector<int>;

const int MOD = 1e9 + 7;

void fastIO() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}

void usaco(string name = "h") {

  freopen((name + ".in").c_str(), "r", stdin);
  freopen((name + ".out").c_str(), "w", stdout);
}

void solve() {
  int s, n;
  cin >> s >> n;

  vector<vi> items(n, vi(3, 0));

  for (int i = 0; i < n; i++)
    cin >> items[i][0] >> items[i][1] >> items[i][2];

  sort(items.begin(), items.end(), [](vi &a, vi &b) {
    if (a[0] == b[0]) {
      if (a[1] == b[1]) {
        return a[2] > b[2];
      } else {
        return a[1] < b[1];
      }
    } else {
      return a[0] < b[0];
    }
  });

  vector<vll> dp(s + 1, vll(n + 1, 0LL));

  for (int i = 1; i <= s; i++) {
    for (int j = 1; j <= n; j++) {

      auto item = items[j - 1];

      for (int k = 0; k <= min(i / item[1], item[2]); k++) {
        dp[i][j] = max(dp[i][j], k * item[0] + dp[i - (k * item[1])][j - 1]);
      }
    }
  }

  ll maxS = 0LL;
  each(row, dp) each(it, row) maxS = max(maxS, it);

  cout << maxS << endl;
}

int main() {
  // usaco();
  fastIO();
  solve();

  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void usaco(std::string)':
knapsack.cpp:32:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   freopen((name + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |   freopen((name + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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