Submission #1269350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269350		pwal	Knapsack (NOI18_knapsack)	C++17	37 / 100	1 ms	328 KiB

knapsack

#include <iostream>
#include<vector>
#define LL long long
struct items{
	LL v, w;
};

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int s,n;
	std::cin>>s>>n;
	
         std::vector<items> Items;
	 int j=0;
	for(int i=0;i<n;++i){
		int v,w,k;
		std::cin>>v>>w>>k;
		int c=1;
		while(c<k)
		{
			k=k-c;
			Items.push_back({v*c,w*c});
			c=c*2;

		}
		Items.push_back({v*k,w*k});
	}

	std::vector<LL> dp(s+1,0);
for(int i=0;i<(int)Items.size();i++)
{
	for(int j=s;j>=Items[i].w;j--)
		dp[j]=std::max(dp[j],dp[j-Items[i].w]+Items[i].v);
}


	std::cout<<dp[s]<<'\n';
	
		return 0;


}

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