Submission #499368

#	Time	Username	Problem	Language	Result	Execution time	Memory
499368		ojuzuser12	Knapsack (NOI18_knapsack)	C++17	100 / 100	151 ms	35116 KiB

knapsack

// https://oj.uz/problem/view/NOI18_knapsack
#include <bits/stdc++.h>
using namespace std;

long long dp[2005][2005];
vector<pair<int, int>> items[2005]; // items with a certain weight
int S, N;

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a > b;
}

int main() {
	cin >> S >> N;
	for(int i = 0; i < N; i++) {
		int V, W, K; cin >> V >> W >> K;
		items[W].push_back({V, K});
	}
	for(int i = 1; i <= S; i++) {
		sort(items[i].begin(), items[i].end(), cmp);
	}
	for(int i = 1; i <= S; i++) { // items with first i weights
		for(int w = 1; w <= S; w++) { // weight in dp is i
			int weight = 0, num_current = 0, item_ptr = 0;
			long long profit = 0;
			dp[i][w] = dp[i - 1][w];
			while(weight <= w && item_ptr < items[i].size()) {
				dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + profit);
				weight += i; // current weight is i
				num_current++;
				if(num_current > items[i][item_ptr].second) {
					item_ptr++;
					num_current = 1;
				}
				if(item_ptr < items[i].size()) profit += (long long) items[i][item_ptr].first;
			}
		}
	}
	long long ans = 0;
	for(int i = 1; i <= S; i++) ans = max(ans, dp[S][i]);
	cout << ans << '\n';
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:27:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    while(weight <= w && item_ptr < items[i].size()) {
      |                         ~~~~~~~~~^~~~~~~~~~~~~~~~~
knapsack.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(item_ptr < items[i].size()) profit += (long long) items[i][item_ptr].first;
      |        ~~~~~~~~~^~~~~~~~~~~~~~~~~

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