Submission #1176452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176452		embi	Knapsack (NOI18_knapsack)	C++20	100 / 100	106 ms	38356 KiB

knapsack

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define vi vector<ll>
#define vll vector<ll> 
#define all(x) (x).begin() , (x).end()

void dbg(){
	cerr << endl;
}
template<typename Head , typename... Tail>
void dbg(Head h , Tail... t){
	cerr << h << " ";
	dbg(t...);
}

#ifdef EMBI_DEBUG
#define debug(...) cerr << "(" << #__VA_ARGS__  << "): ", dbg(__VA_ARGS__)
#else 
#define debug(...)
#endif

const ll max_n = 1e5 + 9;
const ll inf = 1e9 + 9;
const ll mod = 1e9 + 7;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
ll power(ll a , ll b)
{
    ll prod = 1;
    while(b)
    {
        if(b&1)
        prod = (prod*a)%mod;
        a = (a*a)%mod;
        b >>= 1;
    }
    return prod;
}

/*

	fun(i, j, rem) = max(fun(i+1, 0, rem)
	, if (j+1 <= K[i]) fun(i, j+1, rem - W[i]) + V[i])
	
	TC: S * (SlogS) 
	Mem: O(N * S)
	
	
	We convert our initial arrayy in the following way
	Map<ll, vector<pair<ll ,ll>>> 
	
	Key --> weight
	Value --> vector of pairs {V[i], K[i]} sorted in descending order.
	
	Now If we convrt this map to a vector of pair with first element being key and second being the value
	then there will not be any duplicates.
	
	
*/

ll S, n;
vector<ll> v, w, k;

void solve(){
	cin >> S >> n;
	v.resize(n);
	w.resize(n);
	k.resize(n);
	
	for (ll i = 0 ; i < n ; i++) {
		cin >> v[i] >> w[i] >> k[i];
	}
	
	map<ll , vector<pair<ll ,ll>>> m;
	for (ll i = 0 ; i < n ; i++) {
		m[w[i]].pb({v[i], k[i]});
	}
	
	vector<pair<ll , vector<pair<ll,ll>>>> a;
	
	for (auto it : m) {
		a.push_back(it);
	}
	
	sort(all(a));
	for (auto &it : a) {
		sort(all(it.second), greater<pair<ll,ll>> ());
	}
	
	vector<vector<ll>> dp((int)a.size() + 1, vector<ll> (S+1));
	
	for (ll i = 0 ; i < a.size() ; i++) {
		for (ll j = 1 ; j <= S ; j++) {
			dp[i+1][j] = dp[i][j];
			ll idx = 0, toRem = 0, value = 0, currCnt = 0;
			while (toRem <= j && idx < a[i].second.size()) {
				toRem += a[i].first;
				value += a[i].second[idx].first;
				currCnt++;
				if (currCnt == a[i].second[idx].second) {
					idx++;
					currCnt = 0;
				}
				
				if (toRem > j) break;
				
				dp[i+1][j] = max(dp[i+1][j], dp[i][j-toRem] + value);
			}
		}
	}
	
	ll ans = 0;
	for (ll i = 0 ; i <= S ; i++) {
		ans = max(ans , dp[(ll)a.size()][i]);
	}
	
	cout << ans << "\n";
}
signed main(){
    ll t = 1;
    // cin >> t;
    for (ll i = 1 ; i <= t ; i++) {
        solve();
    }
}

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