Submission #524819

#	Time	Username	Problem	Language	Result	Execution time	Memory
524819		rsjw	Knapsack (NOI18_knapsack)	C++17	0 / 100	1 ms	344 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,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);
		}
	}
	for(i=1;i<=N;i++)
		for(j=m;j>=w[i];j--)
			f[j]=max(f[j],f[j-w[i]]+v[i]);
	printf("%d",f[m]);
	return 0;
}

Compilation message (stderr)

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

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