Submission #942462

#	Time	Username	Problem	Language	Result	Execution time	Memory
942462		Sunbae	Knapsack (NOI18_knapsack)	C++17	100 / 100	78 ms	36808 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//อ่าน slide บนรถ อ่านรูปที่ like -> 7:05
ll dp[2005][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 i = 0; i<m; ++i) for(int j = 0; j<=S; ++j) dp[i][j] = -inf;
	dp[0][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 = 0; j<=S; ++j){
			dp[i][j] = max(dp[i][j], dp[i-1][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){
						if(dp[i-1][j-w*curr] != -inf) dp[i][j] = max(dp[i][j], dp[i-1][j-w*curr] + profit);
					}else{
						br = true; break;
					}
				}
				if(br) break;
			}
		}
	}
	ll ans = -inf;
	for(int i = 1; i<m; ++i){
		for(int j = 0; j<=S; ++j){
			ans = max(ans, dp[i][j]);
		}
	}
	printf("%lld", ans);
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  int S, n; scanf("%d %d", &S, &n);
      |            ~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   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