Submission #886640

#	Time	Username	Problem	Language	Result	Execution time	Memory
886640		DP_196	Knapsack (NOI18_knapsack)	C++14	0 / 100	2 ms	604 KiB

knapsack

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }

const int MAXN = 2e5 + 6;
const int MAXM = 4e6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, k;
vector<pair<int, int>> value[2005];
int f[2005][2005]; // f[i][j] 
//là giá trị dinh dưỡng lớn nhất khi dùng j tiền, 
//và xét lần lượt đến thực phẩm có giá là i

void solve() {
	cin >> k >> n;
	
	for (int i = 1; i <= n; i++) {
		int c, e, l;
		cin >> c >> e >> l;
		l = min(l, (int) (k / c) + 1);
		value[c].push_back(make_pair(e, l));
	}

	for (int i = 1; i <= k; i++) {
		sort(value[i].begin(), value[i].end());
		reverse(value[i].begin(), value[i].end());
	} 

	for (int cost = 1; cost <= k; cost++) {
		int sum = 0; 
		
		for (int j = 1; j <= k; j++) f[cost][j] = f[cost - 1][j];

		for (auto it : value[cost]) {
			int nutri = it.first, cnt = it.second;

			for (int i = 1; i <= k; i++) {
				for (int j = 1; j <= min(cnt, (int)(i / cost)); j++) {
					if (sum + j > (k / cost)) break;
					f[cost][i] = max(f[cost][i], f[cost - 1][i - cost * j] + j * nutri);
				}
			}

			sum += cnt;
			if (sum > (k / cost)) break;
		}
	}

	cout << f[k][k];

}

#define TASK "a"
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //   freopen(TASK".inp", "r", stdin);
    //   freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

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