Submission #1231276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231276		behesht	Knapsack (NOI18_knapsack)	C++20	100 / 100	48 ms	10052 KiB

knapsack

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define ld                   long double
#define ll                   long long
#define pb                   push_back
#define arr(x)               array <ll, x>
#define endl                 '\n'
#define int                  long long
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e9 + 24 + (33 / 10); // 33 ---> 34
const int MAXN = 1e5 + 24 + (33 / 10); // 33 ---> 34

vector <arr(2)> v[MAXN];
vector <int> h[MAXN];
int dp[MAXN], dpp[MAXN];

int b[MAXN], w[MAXN], k[MAXN];

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	for(int i = 1; i <= n; i++){
		cin >> b[i] >> w[i] >> k[i];

		v[w[i]].pb({b[i], k[i]});
	}

	for(int i = 1; i <= s; i++){
		sort(v[i].begin(), v[i].end(), greater<arr(2)>());

		int cnt = 0;
		for(auto [z, ted] : v[i]){

			while(ted > 0 && (cnt + 1) <= s / i){
				h[i].pb(z);
				ted--;
				cnt++;
			}
		}
	}

	int ans = 0;

	for(int i = 1; i <= s; i++){ // pref
		
		// d1(i);
		int eli = 0;

		for(int j = 0; j < h[i].size(); j++){ // teded

			eli += h[i][j];

			for(int k = 1; k <= s; k++){ // dp

				if(k - (j + 1) * i < 0)
					continue;
				
				dpp[k] = max(dpp[k], dp[k - (j + 1) * i] + eli);
				// d3(j, k, dpp[k]);
			}
		}

		for(int k = 1; k <= s; k++){
			dp[k] = max(dp[k], dpp[k]);
			dpp[k] = 0;
			ans = max(ans, dp[k]);
		}
	}

	cout << ans << endl;
}

// Ey To Bahane! :_)))

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