Submission #1156896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156896		baoq06	Knapsack (NOI18_knapsack)	C++20	100 / 100	67 ms	17480 KiB

knapsack

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<class X> X sqr(X a) {return a * a;}
template<class X, class Y> bool maximize(X &a, const Y& b) {X eps = 1e-9; return (b > a + eps) ? a = b, 1 : 0;}
template<class X, class Y> bool minimize(X &a, const Y& b) {X eps = 1e-9; return (b + eps < a) ? a = b, 1 : 0;}

void setIO(string NAME = "") {
	if((int) NAME.length() && fopen((NAME + ".inp").c_str(), "r"))
		freopen((NAME + ".inp").c_str(), "r", stdin),
		freopen((NAME + ".out").c_str(), "w", stdout);
}

const int N = 2e3 + 10;
int dp[N][N];
vector<pair<int, int>> weight[N];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int s, n;
	cin >> s >> n;

	for(int i = 1; i <= n; i++) { 
		int v, w, k;
		cin >> v >> w >> k;
		weight[w].push_back({v, k});
	}

	memset(dp, 0, sizeof(dp));
	for(int i = 1; i <= s; i++) {
		sort(rall(weight[i]));
		
		int sumWeight = 0;
		int cur = 0;
		int curVal = 0;

		for(int j = 0; j <= s; j++) {
			if(sumWeight > s) break;
			sumWeight += i;
			if(weight[i].size())
				curVal += weight[i][cur].first;

			for(int k = 0; k <= s; k++) {
				maximize(dp[i][k], dp[i - 1][k]);
				if(k - sumWeight >= 0)
					maximize(dp[i][k], dp[i - 1][k - sumWeight] + curVal);
			}

			if(weight[i].size()) {
				weight[i][cur].second--;
				if(!weight[i][cur].second)
					cur++;
				if(cur == (int) weight[i].size())
					break;
			}
		}
	}

	int ans = 0;
	for(int i = 1; i <= s; i++) {
		for(int j = 1; j <= s; j++)
		maximize(ans, dp[i][j]);
	}

	cout << ans;

	return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:14:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |                 freopen((NAME + ".inp").c_str(), "r", stdin),
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:15:24: 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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27