Submission #680799

#	Time	Username	Problem	Language	Result	Execution time	Memory
680799		MilosMilutinovic	Knapsack (NOI18_knapsack)	C++14	100 / 100	55 ms	4364 KiB

knapsack

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int N = 2020;
const int M = N * N;
int s, n;
int v[M];
int w[M];
int k[M];
ll dp[N];
pair<int, int> b[M];
vector<int> f[N];
int ord[M];

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%d%d", &s, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &v[i], &w[i], &k[i]);
		f[w[i]].push_back(i);
	}
	int m = 0;
	for (int i = 1; i <= s; i++) {
		int sz = (int)f[i].size();
		for (int j = 0; j < sz; j++)
			ord[j] = f[i][j];
		sort(ord, ord + sz, [&](int i, int j) { return v[i] > v[j]; });
		int curS = 0;
		for (int j = 0; j < sz; j++) {
			while(k[ord[j]] > 0 && curS + i <= s) {
				b[m++] = make_pair(v[ord[j]], i);
				k[ord[j]]--;
				curS += i;
			}
		}
	}
	for (int i = 0; i < m; i++) {
		int V = b[i].first;
		int W = b[i].second;
		for (int j = s - W; j >= 0; j--)
			dp[j + W] = max(dp[j + W], dp[j] + V);
	}
	printf("%lld\n", dp[s]);

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d", &s, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d%d", &v[i], &w[i], &k[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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