Submission #475501

#	Time	Username	Problem	Language	Result	Execution time	Memory
475501		dolamanee	Knapsack (NOI18_knapsack)	C++17	100 / 100	157 ms	38784 KiB

knapsack

// Created by ...
#include <bits/stdc++.h>

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pii pair<ll,ll>
#define vec(a) vector<a >
#define all(a) (a).begin(),(a).end()
#define se second
#define fi first
#define inf 0xffffffff
#define int long long
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,b,a) for(ll i=b;i>=a;--i)
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define EACH(x, a) auto _Itr=begin(a);for (auto x=*_Itr;_Itr!=end(a);_Itr=next(_Itr),x=*_Itr)

using namespace std;
using ll = long long;
using ld = long double;
ll md = MD;

template<class... Args> auto Vec(size_t n, Args&&... args) {
	if constexpr(sizeof...(args) == 1)return vector(n, args...);
	else return vector(n, Vec(args...));
}
template<class T, class... Args> void DBS(T t, Args... args) {
	cerr << t;
	if constexpr(sizeof...(args) == 0) cerr << "]\n";
	else cerr << ", ", DBS(args...);
}
#ifdef _DEBUG
#define db(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBS(__VA_ARGS__)
#else
#define db(...) 0
#endif

ll exp(ll a, ll b) {ll r = 1ll; while (b > 0) {if (b & 1) {r = r * (a % md); r = (r + md) % md;} b >>= 1; a = (a % md) * (a % md); a = (a + md) % md;} return (r + md) % md;}
ll gcd(ll a, ll b) {if (b == 0)return a; return gcd(b, a % b);}
template<class T> T Min(T a, T b) {if (a < b)return a; return b;}
template<class T> T Max(T a, T b) {if (a > b)return a; return b;}
const int MX = 1e5, S = 2001;
int dp[S][S], s, n, v[MX], w[MX], cnt[MX];
vec(pii) item[S];
int solve(int id, int rem) {
	if (rem < 0)return -1e12;
	if (id < 0)return 0;
	if (dp[id][rem] != -1)return dp[id][rem];
	int ans = solve(id - 1, rem), currw = 0, currval = 0;
	for (auto&[val, avl] : item[id]) {
		rep(i, 1, avl) {
			currw += id;
			currval += val;
			if (currw > rem)break;
			ans = max(ans, currval + solve(id - 1, rem - currw));
		}
		if (currw > rem)break;
	}
	return dp[id][rem] = ans;
}
void solve() {
	cin >> s >> n;
	int maxx = 0;
	rep(i, 0, n - 1)cin >> v[i] >> w[i] >> cnt[i];
	rep(i, 0, n - 1)item[w[i]].pb({v[i], cnt[i]}), maxx = max(maxx, w[i]);
	rep(i, 0, S - 1)sort(all(item[i])), reverse(all(item[i]));
	memset(dp, -1, sizeof(dp));
	cout << solve(maxx, s);
}

int32_t main() {
	IOS;

	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

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