Submission #782434

#	Time	Username	Problem	Language	Result	Execution time	Memory
782434		makanhulia	Knapsack (NOI18_knapsack)	C++17	29 / 100	101 ms	100860 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][MAXT];
// Vec[i][j] menyatakan state energi j pada saat energi = i
// {Li, Ki}


int main(){
  cin >> t >> n;
  for (int i = 1; i <= n; ++i)
  {
    ll li, ei, ki;
    cin >> li >> ei >> ki;

    vec[0][ei].push_back({li, ki});
  }

  for (int i = 0; i <= t; ++i)
  {
    if (!vec[0][i].empty())
    {
      sort(vec[0][i].begin(), vec[0][i].end());
      for (int j = 1; j <= t; ++j)
      {
        vec[j][i] = vec[0][i];
      }
    }
  }

  for (int i = 0; i <= t; ++i)
  {
    pll pake = {-1, -1};
    // {i yang mana, j berapa}
    for (int j = 0; j <= i; ++j)
    {
      if (vec[i-j][j].empty())
      {
        if (dp[i-j] > dp[i])
        {
          pake = {i-j, -1};
          dp[i] = dp[i-j];
        }
        continue ;
      }

      ll hasil = dp[i-j] + vec[i-j][j].back().first;
      // cout << vec[i-j][j].back().first << "\n";
      if (hasil > dp[i])
      {
        pake = {i-j, j};
        dp[i] = hasil;
      }
    }

    if (pake.first > -1)
    {
      if (pake.second > -1)
      {
        // Kurangi
        vec[pake.first][pake.second].back().second--;
        if (vec[pake.first][pake.second].back().second == 0)
        {
          vec[pake.first][pake.second].pop_back();
        }
      }

      for (int j = 0; j <= t; ++j)
      {
        vec[i][j] = vec[pake.first][j];
      }
    }
  }

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

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

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