Submission #524822

#	Time	Username	Problem	Language	Result	Execution time	Memory
524822		rsjw	Knapsack (NOI18_knapsack)	C++14	100 / 100	69 ms	5024 KiB

knapsack

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int v[100010],w[100010],k[100010];
vector<pair<int,int>> a[2005];
int V[26000],W[26000],N;
long long f[2010];
void add(int x,int y,int t=1){
	while(t--)N++,V[N]=x,W[N]=y;
}
int main(){
	int m,n,i,j;
	scanf("%d%d",&m,&n);
	for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&k[i]);
	for(i=1;i<=n;i++)a[w[i]].push_back(make_pair(-v[i],k[i]));
	for(i=1;i<=m;i++){
		sort(a[i].begin(),a[i].end());
		int count=(m+i-1)/i;
		for(auto j:a[i]){
			if(count==0)break;
			add(-j.first,i,min(count,j.second));
			count-=min(count,j.second);
		}
	}
	long long ans=0;
	for(i=1;i<=N;i++)
		for(j=m;j>=W[i];j--)
			f[j]=max(f[j],f[j-W[i]]+V[i]);
	for(j=m;j>=0;j--)ans=max(ans,f[j]);
	printf("%lld",ans);
	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  scanf("%d%d",&m,&n);
      |  ~~~~~^~~~~~~~~~~~~~
knapsack.cpp:15:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  for(i=1;i<=n;i++)scanf("%d%d%d",&v[i],&w[i],&k[i]);
      |                   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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