Submission #948018

#	Time	Username	Problem	Language	Result	Execution time	Memory
948018		4QT0R	Knapsack (NOI18_knapsack)	C++17	100 / 100	64 ms	44660 KiB

knapsack

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

struct prod{
	ll value;
	ll weight;
	ll quantity;
};

bool sorting(prod a, prod b){
	if (a.weight==b.weight)return a.value>b.value;
	return a.weight<b.weight;
}

ll dp[2003][2003];
prod wej[100003];
ll sum[2003][2003];
ll il[2003];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	ll S,n;
	cin >> S >> n;
	for (int i = 0; i<n; i++){
		cin >> wej[i].value >> wej[i].weight >> wej[i].quantity;
		wej[i].quantity=min(S,wej[i].quantity);
	}
	sort(wej,wej+n,sorting);
	ll iter=0,q;
	for (int i = 1; i<=S; i++){
		q=0;
		while(iter<n && wej[iter].weight==i){
			for (int j = 1; q*i<=S && j<=wej[iter].quantity; j++){
				q++;
				sum[i][q]=sum[i][q-1]+wej[iter].value;
			}
			iter++;
		}
		il[i]=q;
	}
	ll mx=0;
	for (int i = 1; i<=S; i++){
		for (int j = 1; j<=S; j++){
			dp[i][j]=dp[i-1][j];
			iter=1;
			for (int u = j-i; u>=0 && iter<=il[i]; u-=i, iter++){
				dp[i][j]=max(dp[i][j],dp[i-1][u]+sum[i][iter]);
			}
			mx=max(mx,dp[i][j]);
		}
	}
	cout << mx << '\n';
}

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