Submission #739079

#	Time	Username	Problem	Language	Result	Execution time	Memory
739079		bane	Knapsack (NOI18_knapsack)	C++17	100 / 100	281 ms	38812 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;
#define int long long
class Solution{

	private:
	int N, S, V[100001], W[100001], K[100001];
	
	public:
	void init(){
		cin >> S >> N;
		for (int i = 1; i <= N; i++){
			cin >> V[i] >> W[i] >> K[i];
		}
	}
	
	int Solve(){
		vector<pair<int,int>>knapsack[2001];
		for (int i = 1; i<=N; i++){
			knapsack[W[i]].emplace_back(make_pair(V[i], K[i]));
		}
		for (int j = 1; j<=2000; j++){
			sort(knapsack[j].rbegin(), knapsack[j].rend());
		}
		vector<vector<int>>dp(2002, vector<int>(2002, 0));
		for (int weight = 1; weight <= 2000; weight++){					
			for (int total = 0; total<=2000; total++){
				int full = 0;
				int val = 0;
				for (auto item : knapsack[weight]){
					for (int j = 1; j <= (int)item.second; j++){
						full += weight;
						val  += item.first;
						if (full + total <= 2000){
							dp[weight][total + full] = max(dp[weight][total + full], dp[weight - 1][total] + val);
						}else{
							break;
						}
					}
				}
				dp[weight][total] = max(dp[weight][total], dp[weight - 1][total]);
			}
		}	
		int ans = 0;
		for (int i = 0 ; i<=S; i++){
			ans = max(ans, dp[2000][i]);
		}
		return ans;
	}

};

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	Solution resenie;
	resenie.init();
	cout<<resenie.Solve();
	return 0;
}

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