Submission #782437

#	Time	Username	Problem	Language	Result	Execution time	Memory
782437		christinelynn	Knapsack (NOI18_knapsack)	C++17	100 / 100	89 ms	5064 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll MAXT = 2e3 + 5;

ll t, n, dp[MAXT];
vector<pll> vec[MAXT];
// {Li, Ki}

vector<pll> items;
// {Li, Ei}

int main(){
  dp[0] = 0;
  cin >> t >> n;
  for (int i = 0; i < n; ++i)
  {
    ll tmpa, tmpb, tmpc;
    cin >> tmpa >> tmpb >> tmpc;
    vec[tmpb].push_back({tmpa, tmpc});
  }

  for (int i = 1; i <= t; ++i)
  {
    if (vec[i].empty())
    {
      continue ;
    }

    sort(vec[i].begin(), vec[i].end());
    ll cnt = t / i;
    while(cnt > 0) {
      if (vec[i].back().second == 0)
      {
        vec[i].pop_back();
        if (vec[i].empty())
        {
          break ;
        }
      }

      items.push_back({vec[i].back().first, i});
      vec[i].back().second--;
      cnt--;
    }
  }

  for (int i = 0; i < items.size(); ++i)
  {
    pll now = items[i];
    // {Li, Ei}
    // cout << now.first << " " << now.second << "\n";
    for (int j = t; j >= now.second; --j)
    {
      dp[j] = max(dp[j], dp[j-now.second] + now.first);
    }
  }

  // for (int i = 0; i <= t; ++i)
  // {
  //   cout << dp[i] << " ";
  // }

  // cout << "\n";
  cout << dp[t] << "\n";
  return 0;
}

Compilation message (stderr)

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

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