Submission #1273022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273022		horizeen	Knapsack (NOI18_knapsack)	C++17	0 / 100	186 ms	327680 KiB

knapsack

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;

#define all(v)                  v.begin(), v.end()
#define rall(v)                 v.rbegin(), v.rend()
#define sz(v)                   ((int)v.size())

#define rep(i, n)               for(int i = 0; i < (n); i++)

#define pry                     puts("YES")
#define prn                     puts("NO")
#define endl                    '\n'

#define pb                      push_back
#define pr first
#define wh second

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
	int n, s;
	cin >> s >> n;
	// worth, weight
	vector<pair<int,int>> objs;
	rep(i, n){
		ll a, b, c;
		cin >> a >> b >> c;
		rep(j, c)
			objs.pb(make_pair(a, b));

	}
	/*
	 * Iterate over all possible items in a 2 dimensional dp array
	*/
	vector<vector<int>> dp(sz(objs) + 1);
	for (auto &x : dp)
		x.assign(s + 1, 0);
	
	for (int i = 0; i < sz(objs); i++){
		for (int j = 0; j < s+1; j++){
			dp[i + 1][j] = dp[i][j];
			if (j - objs[i].wh  >= 0)
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - objs[i].wh] + objs[i].pr);
		}
	}
	cout << dp[sz(objs)][s] << endl;

}

int32_t main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	int t = 1;
	while(t--){
		solve();	
	}
	return 0;
}

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