Submission #602569

#	Time	Username	Problem	Language	Result	Execution time	Memory
602569		hasan_tawsif	Knapsack (NOI18_knapsack)	C++14	73 / 100	1082 ms	2740 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#ifdef LOCAL
#include "H:\code\codeforces\debug.h"
#else
#define debug(...)
#define sdebug(...)
#endif

//https://oj.uz/problem/view/NOI18_knapsack

const ll inf = (ll) 1e16;

ll dp[2][2005];

void solve() {
	int capacity, n;
	cin >> capacity >> n;

	int profit[n + 1], weight[n + 1], copy[n + 1];
	for (int i = 1; i <= n; ++i) cin >> profit[i] >> weight[i] >> copy[i];

    for (int i = 1; i <= n; ++i) {
    	for (int rem = 1; rem <= capacity; ++rem) {
    		for (int cnt = 1; cnt <= min(copy[i], 2004); ++cnt) {
    			if (rem - (cnt * weight[i]) >= 0) dp[1][rem] = max(dp[1][rem], dp[0][rem - (cnt * weight[i])] + (profit[i] * cnt));
    			dp[1][rem]= max(dp[1][rem], dp[0][rem]);
    		}
    	}
    	for (int rem = 1; rem <= capacity; ++rem) dp[0][rem] = dp[1][rem];
    }
    cout << dp[1][capacity] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
 //   cin >> t;
    while(t--) solve();
}

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