Submission #1274654

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274654		rafsanamin2020	Knapsack (NOI18_knapsack)	C++20	100 / 100	98 ms	33728 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll;
ll MOD = 1E9 + 7, MX = 1E6 + 2;
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  // int T;
  // cin >> T;
  // for (int t = 1; t <= T; t++)
  // {
  int S, N;
  cin >> S >> N;

  vector<int> V(N);
  vector<int> R(N);
  vector<int> K(N);

  vector<vector<int>> group_by_gas_req(S + 1);

  for (int i = 0; i < N; i++)
  {
    cin >> R[i] >> V[i] >> K[i];
    group_by_gas_req[V[i]].push_back(i);
  }

  vector<vector<ll>> dp(S + 1, vector<ll>(S + 1, 0));

  auto compare = [&R](int a, int b)
  {
    return R[a] > R[b];
  };
  for (int i = 1; i <= S; i++)
  {

    sort(group_by_gas_req[i].begin(), group_by_gas_req[i].end(), compare);
    // reverse(group_by_gas_req[i].begin(), group_by_gas_req[i].end());

    // for (int x : (group_by_gas_req[i]))
    // {
    //   cout << R[x] << " ";
    // }
    // cout << "\n";

    for (int j = 1; j <= S; j++)
    {
      ll k_maximum = S / i, val = 0, cumulative_k = 1;

      int k = 1, l = 0;
      while (k_maximum > 0 && l < group_by_gas_req[i].size())
      {

        val += (R[group_by_gas_req[i][l]]);
        // cout << i << " " << j << " " << max(dp[i - 1][j - min(j, k * i)] + (((k * i) <= j) ? val : 0), dp[i - 1][j]) << "\n";
        dp[i][j] = max(max(dp[i - 1][j - min((ll)j, cumulative_k * i)] + (((cumulative_k * i) <= j) ? val : 0), dp[i - 1][j]), dp[i][j]);

        k++;
        cumulative_k++;
        k_maximum--;

        if (k > K[group_by_gas_req[i][l]])
        {
          k = 1;
          l++;
        }
      }

      dp[i][j] = max(dp[i - 1][j], dp[i][j]);
    }
  }

  // for (int i = 1; i < S; i++)
  // {

  //   for (int j = 1; j < S; j++)
  //   {
  //     cout << dp[i][j] << " ";
  //   }
  //   cout << "\n";
  //   // }
  // }
  cout << dp[S][S] << "\n";
}

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