제출 #1326911

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326911		DvcMinh	Knapsack (NOI18_knapsack)	C++20	100 / 100	60 ms	45624 KiB

knapsack

// vegnim
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define setpre(n) fixed << setprecision(n)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mask(n) (1LL << (n))
#define getbit(x, b) (((x) >> (b)) & 1)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORd(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define task ""
#define dbg if (DEBUG_MODE)
const bool DEBUG_MODE = 0;

const int maxN = 1e5+5, maxS = 2005;

int s,n,v[maxN],w[maxN],k[maxN];

namespace sub1
{
  void solve()
  {
    ll ans = 0;
    while (k[1]-- && s - w[1] >= 0){
      ans += v[1];
      s -= w[1];
    }
    cout << ans;
  }
}

namespace sub2
{
  const int maxN = 105;

  int dp[maxN][maxS];

  void solve()
  {
    FOR(i, 1, n){
      FOR(j, 0, s){
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
      }
    }
    cout << dp[n][s];
  }
}

namespace sub3
{
  const int maxN = 1e3+5;

  int dp[maxN][maxS];

  void solve()
  {
    int m = n;
    FOR(i, 1, n){
      REP(j, k[i]-1){
        m++;
        v[m] = v[i];
        w[m] = w[i];
      }
    }
    n = m;
    FOR(i, 1, n){
      FOR(j, 0, s){
        dp[i][j] = dp[i-1][j];
        if (j >= w[i]) dp[i][j] = max(dp[i][j], v[i] + dp[i-1][j-w[i]]);
      }
    }
    cout << dp[n][s];
  }
}

namespace sub4
{
  const int maxN = 4000;

  ll wt[maxN],val[maxN],dp[maxN][maxS];

  void solve()
  {
    int m = 0;
    FOR(i, 1, n){
      for (int j=0; (1 << j) <= k[i]; j++){
        m++;
        wt[m] = (1LL << j) * w[i];
        val[m] = (1LL << j) * v[i];
        k[i] -= (1 << j);
      }
      if (k[i]){
        m++;
        wt[m] = 1LL*k[i] * w[i];
        val[m] = 1LL*k[i] * v[i];
      }
    }
    n = m;
    FOR(i, 1, n){
      FOR(j, 0, s){
        dp[i][j] = dp[i-1][j];
        if (j >= wt[i]) dp[i][j] = max(dp[i][j], val[i] + dp[i-1][j-wt[i]]);
      }
    }
    cout << dp[n][s];
  }
}

namespace sub5
{
  vector<vector<pii>> item;
  ll dp[maxS][maxS];

  void solve()
  {
    item.assign(s+1, vector<pii> {});
    FOR(i, 1, n){
      item[w[i]].pb({v[i], k[i]});
    }
    FOR(i, 1, s){
      sort(all(item[i]), greater<pii>());
    }
    dbg{
      FOR(i, 1, s){
        if (item[i].empty()) continue;
        cout << i<<": ";
        for (auto x : item[i]){
          cout << x.fi<<','<<x.se<<' ';
        }
        cout<<'\n';
      }
    }
    FOR(i, 1, s){
      FOR(j, 0, s){
        dbg cout << "?? "<<i<<','<<j<<'\n';
        dp[i][j] = dp[i-1][j];
        ll sumval = 0;
        int sumw = 0;
        int p = 0, itemcnt = 0;
        while (p < sz(item[i])){
          if (item[i][p].se - itemcnt <= 0){
            p++;
            itemcnt = 0;
            continue;
          }
          if (j < sumw + i){
            break;
          }
          sumw += i;
          sumval += item[i][p].fi;
          itemcnt++;
          dp[i][j] = max(dp[i][j], sumval + dp[i-1][j - sumw]);
          dbg cout << "update with val "<<sumval<<" at "<<i<<','<<j<<" w "<<sumw<<'\n';
        }
      }
    }
    dbg{
      cout << dp[1][1]<<'\n';
    }
    cout << dp[s][s];
  }
}

signed main()
{
  ios_base::sync_with_stdio(NULL); cin.tie(nullptr);
  // freopen("inp.txt","r",stdin);
  cin >> s >> n;
  bool issub2 = (n <= 100);
  bool issub3 = (n <= 100);
  bool issub4 = (n <= 100);
  FOR(i, 1, n){
    cin >> v[i] >> w[i] >> k[i];
    if (k[i] != 1) issub2 = 0;
    if (k[i] > 10) issub3 = 0;
  }
  if (n == 1){
    sub1::solve();
    return 0;
  }
  if (issub2){
    sub2::solve();
    return 0;
  }
  if (issub3){
    sub3::solve();
    return 0;
  }
  if (issub4){
    sub4::solve();
    return 0;
  }
  sub5::solve();
  return 0;
}

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