Submission #966214

#TimeUsernameProblemLanguageResultExecution timeMemory
966214PringKnapsack (NOI18_knapsack)C++17
100 / 100
60 ms3968 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3","unroll-loops") #pragma GCC target("avx2","popcnt","sse4","abm") using namespace std; #ifdef MIKU string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m"; #define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x) void dout() { cout << dbrs << endl; } template <typename T, typename ...U> void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); } #else #define debug(...) 39 #endif #define fs first #define sc second #define mp make_pair #define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++) using ll = long long; typedef pair<int, int> pii; const int MXN = 2005; int n, W; vector<pii> ls[MXN]; vector<int> w, v; int dp[MXN]; void TENKAI(int id, int bnd) { sort(ls[id].begin(), ls[id].end(), greater<pii>()); for (auto &[val, cnt] : ls[id]) { FOR(i, 0, min(bnd, cnt)) { v.push_back(val); w.push_back(id); } bnd -= min(bnd, cnt); if (bnd == 0) break; } } void miku() { int x, y, z; cin >> W >> n; while (n--) { cin >> x >> y >> z; ls[y].push_back(mp(x, z)); } FOR(i, 1, W + 1) TENKAI(i, W / i); FOR(i, 0, v.size()) { for (int j = W; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } cout << *max_element(dp, dp + W + 1) << '\n'; } int32_t main() { cin.tie(0) -> sync_with_stdio(false); cin.exceptions(cin.failbit); miku(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...