Submission #1271979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271979		thuhienne	Knapsack (NOI18_knapsack)	C++20	100 / 100	37 ms	1772 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;

int s,n;
vector <pair <int,int>> temp[2009];

int cnt;
pair <int,int> knapsack[24009];
long long dp[2009];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
//  freopen(".inp","r",stdin);
//  freopen(".out","w",stdout);
	cin >> s >> n;
	for (int i = 1;i <= n;i++) {
		int v,w,k;cin >> v >> w >> k;
		temp[w].push_back({v,k});
	}
	for (int i = 1;i <= s;i++) {
		vector <pair <int,int>>& curr = temp[i];
		sort(curr.begin(),curr.end(),greater <pair <int,int>>());
		int chosen = 0,lim = s/i;
		for (auto x : curr) {
			int ddd = min(lim - chosen,x.second);
			chosen += ddd;
			for (int t = 1;t <= ddd;t++) knapsack[++cnt] = {x.first,i};
			if (chosen == lim) break;
		}
	}
	for (int i = 1;i <= cnt;i++) {
		for (int j = s;j >= knapsack[i].second;j--) {
			dp[j] = max(dp[j],dp[j - knapsack[i].second] + knapsack[i].first);
		}
	}
	cout << dp[s];
}

/*
  Thuong em khi mua thu
  Thuong em sang mua ha
  Thuong em bang qua mua dong,gui gio xuan om em vao long
  Thuong em bao mua mua
  Tham thuong luon bao mua nang
  Thuong yeu em khong doi thay,gio mat em tim toi hao gay ):
*/

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