Submission #1271503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271503		pwal	Knapsack (NOI18_knapsack)	C++17	100 / 100	38 ms	1688 KiB

knapsack

#include <iostream>
#include <vector>
#include <algorithm>
#define LL long long
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 int n,s;
 std::cin>>s>>n;
 int v,w,k;
 std::vector<LL> dp(2001);
 std::vector<std::pair<int,int>> group[2001];
 for(int i=0;i<n;i++)
 {
	 std::cin>>v>>w>>k;
	 group[w].emplace_back(v,k);
	 
 }
 LL answer=0;
 for(int i=0;i<=s;i++)
 {        if(!group[i].empty()){
	 std::sort(group[i].begin(),group[i].end(),std::greater<std::pair<int,int>>());
	 int index=0;
 for(int j=0;j<s/i;j++)
 {
if(index>=group[i].size())break;
for(int k=s;k>=i;k--)
{
	dp[k]=std::max(dp[k],dp[k-i] + group[i][index].first);
	answer=std::max(answer,dp[k]);
}
group[i][index].second--;
if(group[i][index].second==0)index++;
 }
}
 }
std::cout<<answer<<'\n';
	return 0;
}

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