Submission #1220992

#TimeUsernameProblemLanguageResultExecution timeMemory
1220992longggggKnapsack (NOI18_knapsack)C++17
37 / 100
1 ms328 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' #define IN "A.in" #define OUT "A.out" #define DEBUG "debug.out" const int mxN = 100005, INF = (int) 1e9+5; const ll MOD = (ll) 1e9+7, LINF = (ll) 1e18; void solve() { int n, limit; cin >> limit >> n; // (v, w) got k times map <pair <int, int>, int> a; for (int i = 1; i <= n; i++) { int v, w, k; cin >> v >> w >> k; a[{v, w}] += k; } // Binary Decomposition vector <pair <int, int>> items; // (w, v) for (auto &x : a) { int w = x.first.second, v = x.first.first, k = x.second; for (int curr_copy = 1; k > 0; curr_copy <<= 1) { // d *= 2 int use = min(curr_copy, k); items.push_back({w * use, v * use}); k -= use; } } // for (auto &x : items) cerr << x.first << " " << x.second << endl; vector <ll> dp(limit + 1, 0); for (auto &it : items) { int w = it.first, v = it.second; for (int j = limit; j >= w; j--) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[limit] << endl; } signed main() { if (fopen(IN, "r")) { freopen(IN, "r", stdin); freopen(OUT, "w", stdout); freopen(DEBUG, "w", stderr); } ios_base::sync_with_stdio(0); cin.tie(0); // ll t; cin >> t; // while (t--) solve(); }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:47:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         freopen(IN, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(OUT, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~
knapsack.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(DEBUG, "w", stderr);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#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...