Submission #1101835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101835		akamizane	Knapsack (NOI18_knapsack)	C++17	100 / 100	70 ms	36288 KiB

knapsack

#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using pii = pair<long long,int>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 5;

void solve(){
 ll s;
 int n;
 cin >> s >> n;
 map<int, vector<pii>> mp;
 REP(i, n){
  int v, w, k;
  cin >> v >> w >> k;
  mp[w].pb({v, k});
 }
 int m = mp.size();
 vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
 int cur = 0;
 for (auto [w, v] : mp){
  vector<pii> a = v;
  sort(a.begin(), a.end(), [](pii x, pii y){
    return x.fi > y.fi;
  });
  for (int i = 0; i <= s; i++){
    chmax(dp[cur + 1][i], dp[cur][i]);
  }
  int idx1 = 0;
  int idx2 = 0;
  int cnt = 1;
  ll weight;
  ll val = 0;
  while(true){
    weight = cnt * w;
    val += a[idx2].fi;
    idx1++;
    if (weight > s) break;
    for (int i = 0; i + weight <= s; i++){
      chmax(dp[cur + 1][i + weight], dp[cur][i] + val);
    }
    if (idx1 == a[idx2].se){
      idx2++;
      if (idx2 == a.size()){
        break;
      }
      idx1 = 0;
    }
    cnt++;
  }
  cur++;
 }
  cout << *max_element(all(dp[m]));
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:61:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |       if (idx2 == a.size()){
      |           ~~~~~^~~~~~~~~~~

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