제출 #1273099

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273099		horizeen	Knapsack (NOI18_knapsack)	C++17	17 / 100	5 ms	8004 KiB

knapsack

#include "bits/stdc++.h"
#include <utility>

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<ll, ll>> objs;
	rep(i, n){
		int a, b, c;
		cin >> a >> b >> c;
		c = min(c, s);
		for (int pow = 1; pow < c; pow *= 2)
			objs.pb(make_pair(pow * a, pow * b));
		objs.pb(make_pair(c * a, c * b));
	}
	/*
	 * Iterate over all possible items in a 2 dimensional dp array
	*/
	vector<vector<ll>> 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: 17 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27