Submission #780608

#	Time	Username	Problem	Language	Result	Execution time	Memory
780608		myde	Knapsack (NOI18_knapsack)	C++17	73 / 100	142 ms	262144 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define ioss                    \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0)
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
int t, n;
int l[100004], e[100004], k[100004];

signed main()
{
  ioss;
  cin >> t >> n;
  for (int i = 1; i <= n; i++){
    cin >> l[i] >> e[i] >> k[i];
  }

  int dp[n + 1][t + 1];
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= t; j++){
      dp[i][j] = 0;
    }
  }


  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= t; j++)
    {
      dp[i][j] = dp[i - 1][j];
      // cout << dp[i][j] << ' ';
      for (int x = 1; x <= k[i]; x++)
      {
        if (x * e[i] > j)
          break;
        dp[i][j] = max(dp[i - 1][j - (x * e[i])] + (x * l[i]), dp[i][j]);
      }

      // cout << dp[i][j] << ' ';
    }
    cout << '\n';
  }
  cout << dp[n][t] << endl;
}

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