Submission #529315

#	Time	Username	Problem	Language	Result	Execution time	Memory
529315		TruaShamu	Knapsack (NOI18_knapsack)	C++17	0 / 100	21 ms	44060 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

int main() {
	int maxWeight, N;
	cin >> maxWeight >> N;
	vector<vector<pi>> items(maxWeight + 1, vector<pi>());
	
	for (int curW = 0; curW < N; curW++) {
		int V, W, K;
		cin >> V >> W >> K;
		items[W].pb({ V, K });
	}

	for (int curW = 0; curW <= maxWeight; curW++) {
		sort(all(items[curW]), greater<pi>());
	}

	int maxItems = 0;
	for (int curW = 1; curW <= maxWeight; curW++) {
		maxItems += maxWeight / curW;
	}

	vector<vi> dp(maxItems + 1, vi(maxWeight + 1, 0));
	int numItems = 1;
	for (int curW = 1; curW <= maxWeight; curW++) {
		if (items[curW].size() == 0) {
			continue;
		}
		int idx = 0;
		int copies = items[curW][0].second;

		for (int amt = 0; amt < maxWeight / curW; amt++) {
			for (int cur = 1; cur <= maxWeight; cur++) {
				dp[numItems][cur] = dp[numItems - 1][cur];
				if (cur - curW >= 0) {
					dp[numItems][cur] = max(dp[numItems][cur], dp[numItems - 1][cur - curW] + items[curW][idx].f);
				}
			}
			numItems++;
			copies--;
			if (copies == 0) {
				idx++;
				if (idx >= items[curW].size()) {
					break;
				}
				copies = items[curW][idx].s;
			}
		}
	}
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if (idx >= items[curW].size()) {
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |  freopen((name+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:15:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |  freopen((name+".out").c_str(),"w",stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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