제출 #1279466

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1279466		skandaaithal	Knapsack (NOI18_knapsack)	C++20	100 / 100	52 ms	1724 KiB

knapsack

#include <bits/stdc++.h>
#include <cstdio>
#include <ios>

#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define endl "\n"

// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for (auto& a: x)

using namespace std;
template<typename T> ostream& operator<<(ostream& out, vector<T>& a){for (auto &x: a) out << x << " "; out << endl; return out;} 
const int mxN = 1e5+1, mxK = 21;

const long long MOD = 998244353;
long long modpow (long long a ,long long b) {long long res = 1;a %= MOD;while (b > 0) {if (b & 1) res = (res * a) % MOD;a = (a * a) % MOD;b >>= 1;}return res;}
long long modinv ( long long q ) {return modpow (q , MOD - 2);}

void solution() {
  int S, N; cin >> S >> N;
  map<int, vector<array<int, 2>>> mp;
  FOR(i, 0, N){
    int v, w, k; cin >> v >> w >> k;
    mp[w].push_back({v, k});
  }
  each(a, mp){
    sort(rall(a.second));
  }
  vector<int> dp(S+1, 0);
  each(a, mp){
    ROF(i, 0, S+1){
      int tot = 0, val=0;
      bool f=0;
      each(w, a.second){
        FOR(k, 1, w[1]+1){
          tot++; val += w[0];
          if (tot*a.first <= i){
            dp[i] = max(dp[i], dp[i-tot*a.first]+val);
          }
          else {f=1; break;}
        }
        if (f) break;
      }
    }
  }
  cout << dp[S] << endl;
}

int main() {
  ios_base::sync_with_stdio(false); //cin.tie(nullptr);
  // freopen("in.txt", "r", stdin); freopen("snakes.out", "w", stdout);
  solution();
  return 0;
}

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