Submission #1265636

#TimeUsernameProblemLanguageResultExecution timeMemory
1265636tkhoi13Knapsack (NOI18_knapsack)C++20
100 / 100
146 ms124080 KiB
#include <bits/stdc++.h> #define ll long long #define db double #define pii pair<int, int> #define fi first #define se second #define pb push_back #define all(x) begin(x), end(x) #define allr(x) rbegin(x), rend(x) #define szx(x) ((int)(x).size()) #define FOR(i, a, b) for (int i = a, _b = (b); i <= _b; ++i) #define ROF(i, a, b) for (int i = a, _b = (b); i >= _b; --i) #define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i) #define endl '\n' #define inf 1000000007 #define mod 1000000007 using namespace std; void setIO(string filename = "") { ios::sync_with_stdio(0); cin.tie(0); if (!filename.empty()) { if (ifstream(filename + ".in")) { freopen((filename + ".in").c_str(), "r", stdin); freopen((filename + ".out").c_str(), "w", stdout); } } } void solve() { int s, n; cin >> s >> n; map<int, vector<pii>> mp; REP(_, n) { int v, w, k; cin >> v >> w >> k; mp[w].pb({v, k}); } vector<pii> x; for (auto [wei, pi] : mp) { sort(all(pi), [&](pii& a, pii& b) { return a.fi > b.fi; }); int cnt = 0, i = 0; while (cnt < s / wei && i < szx(pi)) { x.pb({pi[i].fi, wei}); cnt++; pi[i].se--; if (!pi[i].se) i++; } // cout << "log: " << cnt << ' ' << wei << endl; } // for (auto [a, b] : x) cout << a << ' ' << b << endl; // cout << szx(x) + 1 << endl; vector<vector<int>> dp(szx(x) + 1, vector<int>(s + 1)); // dp[0][s] = 0; FOR(i, 1, szx(x)) { FOR(j, 0, s) { dp[i][j] = dp[i - 1][j]; if (j >= x[i - 1].se) dp[i][j] = max(dp[i][j], dp[i - 1][j - x[i - 1].se] + x[i - 1].fi); } } cout << dp[szx(x)][s]; } int main() { // setIO("spainting"); int t = 1; // cin >> t; while (t--) solve(); }

Compilation message (stderr)

knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:25:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |             freopen((filename + ".in").c_str(), "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:26:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |             freopen((filename + ".out").c_str(), "w", stdout);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...