제출 #1242241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1242241		wedonttalkanymore	Knapsack (NOI18_knapsack)	C++20	100 / 100	220 ms	1624 KiB

knapsack

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// #define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e5 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;

int s, n;
int v[N], w[N], k[N];
int dp[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i] >> k[i];
		k[i] = min(k[i], 2000);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; k[i] > 0; j *= 2) {
			int now = min(j, k[i]);
			int val = now * v[i];
			int weight = now * w[i];
			if (weight > s) break;
			for (int x = s; x >= weight; x--) {
				if (x >= weight) dp[x] = max(dp[x], dp[x - weight] + val);
			}
			k[i] -= now;
		}
	}
	int ans = 0;
	for (int i = 0; i <= s; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
    return 0;
}

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