Submission #760965

#	Time	Username	Problem	Language	Result	Execution time	Memory
760965		bzhu	Knapsack (NOI18_knapsack)	C++14	100 / 100	76 ms	35152 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

bool larger(pair<int, int> a, pair<int, int> b) {
  return (a > b);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  long long s, n;
  cin >> s >> n;
  map<int, vector<pair<int, int> > > inputs;
  for (long long i=0; i<n; i++) {
    long long value, weight, quantity;
    cin >> value >> weight >> quantity;
    if (weight <= s && quantity > 0) inputs[weight].push_back(pair<int, int> (value, quantity));
  }
  vector<vector<long long> > dp(inputs.size() + 1, vector<long long> (s + 1, -500));
  dp[0][0] = 0;
  int itePosition = 1;
  for (map<int, vector<pair<int, int> > >::iterator ite=inputs.begin(); ite!=inputs.end(); ite++, itePosition++) {
    sort(ite->second.begin(), ite->second.end(), larger);
    for (int i=0; i<=s; i++) {
      dp[itePosition][i] = dp[itePosition - 1][i];
      long long index = 0, quantity = 0, totalValue = 0;
      for (long long copies=1; copies*ite->first<=i && index<ite->second.size(); copies++) {
	totalValue += ite->second[index].first;
	if (dp[itePosition - 1][i - copies * ite->first] != -500) {
	  dp[itePosition][i] = max(dp[itePosition][i], dp[itePosition - 1][i - copies * ite->first] + totalValue);
	}
	quantity++;
	if (quantity == ite->second[index].second) {
	  quantity = 0;
	  index++;
	}
      }
    }
  }
  long long result = 0;
  for (int i=0; i<=s; i++) {
    result = max(result, dp[inputs.size()][i]);
  }
  cout << result << endl;
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:61: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |       for (long long copies=1; copies*ite->first<=i && index<ite->second.size(); copies++) {
      |                                                        ~~~~~^~~~~~~~~~~~~~~~~~~

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