Submission #780458

#	Time	Username	Problem	Language	Result	Execution time	Memory
780458		myde	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	340 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);
  vector<pair<int, int>> v;
  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++)
  {
    if (!simp[i].size())
      continue;
    sort(simp[i].begin(), simp[i].end(), comp);
    int cost = 0, val = 0;
    bool stat = true;
    for (auto j : simp[i])
    {
      if (!stat)
        break;
      int temp = j.second;
      for (int k = 0; k < temp; k++)
      {
        cost += i;
        val += j.first;
        // cout<<cost<<" "<<val<<endl;
        if (cost > N)
        {
          stat = false;
          break;
        }
        v.push_back({val, cost});
      }
    }
  }

  vector<int> dp(N + 1, 0);

  for (auto i : v)
  {
    vector<int> temp = dp;
    for (int j = i.second; j <= N; j++)
      temp[j] = max(temp[j], dp[j - i.second] + i.first);
    dp = temp;
  }

  cout << dp[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: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27