Submission #963014

#	Time	Username	Problem	Language	Result	Execution time	Memory
963014		ezluci	Knapsack (NOI18_knapsack)	C++17	100 / 100	40 ms	3784 KiB

knapsack

#ifdef EZ
   #include "./ez/ez.h"
#else
   #include <bits/stdc++.h>
#endif
#define mp make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
void EZinit() {
   #ifndef EZ
   cin.tie(0)->sync_with_stdio(0);
   #else
   freopen("test.in", "r", stdin);
   freopen("test.out", "w", stdout);
   #endif
}



int main()
{
   EZinit();

   int s, n;   cin >> s >> n;
   vector<int> dp(s+1);
   vector<vector<pair<int,int>>> byWeight(2001);
   for (int i = 1; i <= n; ++i)
   {
      int v, w, k;   cin >> v >> w >> k;
      byWeight[w].pb(mp(v, k));
   }

   for (int w = 1; w <= s; ++w)
   {
      sort(byWeight[w].begin(), byWeight[w].end(), greater<pair<int,int>>());
      int used = 0;  vector<int> spv{0};
      for (int i = 0; i < byWeight[w].size() && used < s/w; ++i)
         for (; used < s/w && byWeight[w][i].se; ++used, byWeight[w][i].se--)
            spv.pb(spv.back() + byWeight[w][i].fi);
      
      for (int i = s; i >= w; --i)
         for (int j = 1; j < spv.size() && i - j*w >= 0; ++j)
            dp[i] = max(dp[i], dp[i - j*w] + spv[j]);
   }

   cout << *max_element(dp.begin(), dp.end());
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:40:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |       for (int i = 0; i < byWeight[w].size() && used < s/w; ++i)
      |                       ~~^~~~~~~~~~~~~~~~~~~~
knapsack.cpp:45:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |          for (int j = 1; j < spv.size() && i - j*w >= 0; ++j)
      |                          ~~^~~~~~~~~~~~

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