Submission #942466

#	Time	Username	Problem	Language	Result	Execution time	Memory
942466		Sunbae	Knapsack (NOI18_knapsack)	C++17	100 / 100	71 ms	4568 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll dp[2005];
array<int,3> Op[100005];
vector<pair<int,int>> vec[2005];
const ll inf = 1e15;
signed main(){
	int S, n; scanf("%d %d", &S, &n);
	vector<int>C;
	for(int i = 0, Vi, Wi, Ki; i<n; ++i){
		scanf("%d %d %d", &Vi, &Wi, &Ki);
		Op[i] = {Vi, Wi, Ki};
		C.push_back(Wi);
	}
	C.push_back(-1);
	sort(C.begin(), C.end());
	C.resize(unique(C.begin(), C.end()) - C.begin());
	for(int i = 0; i<n; ++i){
		int Vi = Op[i][0], Wi = Op[i][1], Ki = Op[i][2];
		vec[upper_bound(C.begin(), C.end(), Wi) - C.begin() - 1].emplace_back(Vi, Ki);
	}
	int m = C.size();
	for(int j = 1; j<=S; ++j) dp[j] = -inf;
	dp[0] = 0;
	for(int i = 1; i<m; ++i){
		sort(vec[i].begin(), vec[i].end(), greater<pair<int,int>>());
		ll w = C[i];
		for(int j = S; j>=0; --j){
			bool br = false;
			ll curr = 0, profit = 0;
			for(pair<int,int> it: vec[i]){
				ll val = it.first, no = it.second;
				for(int cnt = 1; cnt<=no; ++cnt){
					++curr; profit += val;
					if(j>=w*curr){
						dp[j] = max(dp[j], dp[j-w*curr] + profit);
					}else{
						br = true; break;
					}
				}
				if(br) break;
			}
		}
	}
	ll ans = -inf;
	printf("%lld", *max_element(dp, dp+S+1));
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:46:5: warning: unused variable 'ans' [-Wunused-variable]
   46 |  ll ans = -inf;
      |     ^~~
knapsack.cpp:9:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  int S, n; scanf("%d %d", &S, &n);
      |            ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d %d %d", &Vi, &Wi, &Ki);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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