Submission #1074431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074431		Lukamagic77	Knapsack (NOI18_knapsack)	C++17	100 / 100	37 ms	3672 KiB

knapsack

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

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int s, n; cin >> s >> n;
    vector items(s + 1, vector<pair<int,int>>());
    for(int i = 0; i < n; ++i) {
        int w, v, k; cin >> v >> w >> k;
        items[w].push_back({v, k});
    }
    for(int i = 1; i <= s; ++i) {
        if(items[i].empty()) continue;
        sort(items[i].begin(), items[i].end(), greater<>());
    }

    vector<int64_t>dp(s + 1);
    for(int i = 1; i <= s; ++i) {
        if(items[i].empty()) continue;
        for(int j = 1, it = 0; i * j <= s && it < items[i].size(); ++j) {
            auto &[v, k] = items[i][it];
            for(int w = s; w >= i; w--) {
                dp[w] = max(dp[w], dp[w - i] + int64_t(v));
            }
            k--;
            if(k == 0) ++it;
        }
    }
    cout << dp.back() << '\n';
    return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:71:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 1, it = 0; i * j <= s && it < items[i].size(); ++j) {
      |                                              ~~~^~~~~~~~~~~~~~~~~

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