Submission #1237923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237923		SG2Alok	Knapsack (NOI18_knapsack)	C++20	100 / 100	57 ms	4168 KiB

knapsack

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
typedef long long ll;
using namespace __gnu_pbds;
#define endl '\n'
#define hitaf ios_base::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
 
template <typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>;
 
const ll MOD = 1e9 + 7;
const ll MOD1 = 998244353;
const ll INF = 4500000000000000000LL;
const ll INF1 = 1e18;
const ll mod1 = 6900000469;
const ll mod2 = 698000002369;
const int block = 160;

int n, m, k, q, a[1200005], b[500005], c[500005];
string s, s1, s2;

int main() {
    hitaf
	int T = 1;
//	cin >> T;
	
	while(T--){
		cin >> m >> n;
		
		for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
		
		vector<vector<pair<ll, ll>>> val(m + 2);
		for(int i = 1; i <= n; i++){
			val[b[i]].push_back({a[i], c[i]});
		}
		
		vector<ll> dp(m + 2, -INF);
		dp[0] = 0;
		for(int i = 1; i <= m; i++){
			sort(val[i].begin(), val[i].end(), [&](pair<ll, ll> x, pair<ll, ll> y){
				if(x.fi == y.fi) return x.se > y.se;
				return x.fi > y.fi;	
			});
			
			vector<ll> pref(m + 2);
			ll sum = 0, lst = 0;
			for(int j = i, idx = 0; j <= m && idx < val[i].size(); j += i){
				sum += val[i][idx].fi;
				val[i][idx].se--;
				if(val[i][idx].se == 0){
					idx++;
				}
				
				pref[j] = sum;
				lst = j;
			}
			
			for(int j = m; j >= 0; j--){
				for(int k = lst; k >= 0; k -= i){
					if(j < k) continue;
					dp[j] = max(dp[j], dp[j - k] + pref[k]);
				}
			}
		}
		
		ll maks = 0;
		for(int j = 0; j <= m; j++) maks = max(maks, dp[j]);
		
		cout << maks << endl;
	}
}

/*


	8 3 4 2 1 5 7 6
	1 5 6 7 2 4 3 8

*/

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