Submission #762032

#	Time	Username	Problem	Language	Result	Execution time	Memory
762032		DP_196	Knapsack (NOI18_knapsack)	C++14	100 / 100	64 ms	2620 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 = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, s;
int64_t f[2005];
priority_queue<int64_t, vector<int64_t>, greater<int64_t>> g[2005];

void add(int w, int v, int cnt) {
	int64_t x = 1LL * w * cnt, y = 1LL * v * cnt;
	if (x <= s) {
		if (sz(g[x]) <= s / x + 1) {
			g[x].push(y);
		}
		else {
			g[x].pop();
			g[x].push(y);
		}
	}
}

void solve() {
	cin >> s >> n;
	
	for (int i = 1; i <= n; i++) {
		int v, w, k;
		cin >> v >> w >> k;
		
		int sum = 0;
		for (int j = 0; j <= 11; j++) {
			if (k >= MASK(j)) {
				add(w, v, MASK(j));
				k -= MASK(j);
				sum += MASK(j);
				if (sum > s) break;
			}
		}
		if (sum < s && k > 0) add(w, v, k);
	}
	
	for (int i = 1; i <= s; i++) {
		while (sz(g[i])) {
			int x = g[i].top();
			for (int j = s; j >= i; --j) maximize(f[j], f[j - i] + x);
			g[i].pop();
		}
	}

	cout << f[s];
}

#define TASK "ALLOW"
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: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27