Submission #1279060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279060		skandaaithal	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	1608 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;
  vector<array<int, 3>> a(N); // (V, W, K)
  FOR(i, 0, N) cin >> a[i][0] >> a[i][1] >> a[i][2];
  vector<int> dp(S+1, 0);
  FOR(i, 0, N){
    ROF(w, 0, S+1){
      FOR(k, 1, a[i][2]+1){
        if (w - k*a[i][1] < 0) break;
        dp[w] = max(dp[w], dp[w - k*a[i][1]]+k*a[i][0]);
      }
    }
  }
  int ans = 0;
  FOR(i, 0, S+1) ans = max(ans, dp[i]);
  cout << ans << 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: 0 / 27