Submission #780483

#	Time	Username	Problem	Language	Result	Execution time	Memory
780483		myde	Knapsack (NOI18_knapsack)	C++17	100 / 100	69 ms	34176 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define ff first
#define ss second
#define inp_v(vec)    \
  for (auto &i : vec) \
    cin >> i;
#define prt_v(vec)   \
  for (auto i : vec) \
    cout << i << endl;
#define MS(x) memset(x, 0, sizeof(x))
#define gcd(a, b) __gcd(a, b);
#define lcm(a, b) (a * (b / gcd(a, b)))
#define lb lower_bound
#define ub upper_bound
bool chmin(int &a, int b)
{
  return b < a ? a = b, true : false;
}
bool chmax(int &a, int b) { return b > a ? a = b, true : false; }
bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
  return a.first > b.first;
}
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;

  vector<vector<pair<int, int>>> simp(N + 5), v(N + 5);
  for (int i = 0; i < M; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;
    simp[b].push_back({a, c});
  }

  for (int i = 1; i <= N; i++)
  {
    sort(simp[i].begin(), simp[i].end(), comp);
    int cost = 0, val = 0;
    bool stat = true;
    for (auto j : simp[i])
    {
      if (!stat)
        break;
      for (int k = 0; k < j.second; k++)
      {
        cost += i;
        val += j.first;
        // cout<<cost<<" "<<val<<endl;
        if (cost > N)
        {
          stat = false;
          break;
        }
        v[i].push_back({val, cost});
      }
    }
  }

  int dp[N + 1][N + 1];
  memset(dp, 0, sizeof(dp));
  for (int i = 1; i <= N; i++)
  {
    if (v[i].size())
    {
      for (auto j : v[i])
      {
        for (int k = 0; k <= N; k++)
        {
          if (k >= j.second)
          {
            dp[i][k] = max(max(dp[i][k], dp[i - 1][k]), dp[i - 1][k - j.second] + j.first);
          }
          else
          {
            dp[i][k] = max(dp[i][k], dp[i - 1][k]);
          }
        }
      }
    }
    else
    {
      for (int k = 0; k <= N; k++)
      {
        dp[i][k] = dp[i - 1][k];
      }
    }
  }

  cout << dp[N][N] << '\n';
  // dp[0][0]=0;
  // for(int i=1;i<=N;i++){
  //     if(tot[i]){
  //         for(int j=1;j<=N;j++){
  //             int idx=1, cur=v[i][idx].first, cur2=v[i][idx].second, sz=v[i].size();
  //             int k=0;

  //         }
  //     }
  // }
  return 0;
}

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