Submission #782042

#	Time	Username	Problem	Language	Result	Execution time	Memory
782042		devariaota	Knapsack (NOI18_knapsack)	C++17	100 / 100	227 ms	252884 KiB

knapsack

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

#define int long long
const int lim = 100005;
int t, n, val[lim], cost[lim], freq[lim], dp[25005][2005];

vector<pair<int, int>> bycost[lim];
vector<pair<int, int>> item;

signed main() {
  
  cin >> t >> n;
  for (int i = 0; i < n; i++) {
    cin >> val[i] >> cost[i] >> freq[i];
    bycost[cost[i]].push_back({val[i], freq[i]});
  }

  for (int i = 1; i <= t; i++) {
    sort(bycost[i].begin(), bycost[i].end(), greater<pair<int, int>>());
  }

  int total = 0, value = 0;
  // item.push_back({0, 0});
  for (int i = 1; i <= t; i++) {
    total = 0;
    value = 0;
    for (auto j: bycost[i]) {
      if (total > t) break;
      for (int k = 1; k <= j.second; k++) {
        total += i;
        value += j.first;
        if (total > t) break;
        item.push_back({j.first, i});
      }
    }
  }

  // for (auto i: item) {
  //   cout << i.first << " " << i.second << endl;
  // }

  for (int i = 0; i < item.size(); i++) {
    for (int j = 1; j <= t; j++) {
      if (i-1 < 0) dp[i][j] = 0;
      else dp[i][j] = dp[i-1][j];
      if (j >= item[i].second) {
        dp[i][j] = max(dp[i][j], dp[i-1][j-item[i].second]+item[i].first);
      }
    }
  }

  cout << dp[item.size()-1][t] << endl;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:43:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   for (int i = 0; i < item.size(); i++) {
      |                   ~~^~~~~~~~~~~~~

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