Submission #779435

#	Time	Username	Problem	Language	Result	Execution time	Memory
779435		myde	Knapsack (NOI18_knapsack)	C++17	49 / 100	86 ms	262144 KiB

knapsack

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

const int MAXN = 1e5 + 5;
int s, n, v, w, k;
vector<pair<int, int>> items;

int main()
{
  cin >> s >> n;
  // pair<int, pair<int, int>> p[n + 1];

  for (int i = 1; i <= n; i++)
  {
    // cin >> p[i].first >> p[i].second.first >> p[i].second.second;
    cin >> v >> w >> k;
    for (int j = 1; j <= min(k, (s + w - 1) / w); j++)
    {
      items.push_back({v, w});
    }
  }

  n = items.size();
  int dp[n + 1][s + 1];
  for (int i = 0; i <= s; i++)
    dp[0][i] = 0;

  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= s; j++)
    {
      dp[i][j] = dp[i - 1][j];
      if (j >= items[i - 1].second)
      {
        dp[i][j] = max(dp[i][j], dp[i - 1][j - items[i - 1].second] + items[i - 1].first);
      }

      // cout << ":: " << i << ' ' << j << ' ' << dp[i][j] << '\n';
    }
  }

  cout << dp[n][s] << '\n';
}

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