제출 #890579

#제출 시각아이디문제언어결과실행 시간메모리
890579Flan312Knapsack (NOI18_knapsack)C++17
0 / 100
24 ms348 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define eb emplace_back #define task "" #define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout); #define fi first #define se second #define pii pair <ll, ll> #define tii tuple <int, int, int> using namespace std; const int nmax = 2002; int s, n, v[nmax], w[nmax], k[nmax]; int mxk = 0; void sub23() { vector<ll> dp(s + 1, 0); for (int i = 1; i <= n; ++i) for (int j = s; j >= w[i]; --j) for (int use = k[i]; use >= 0; --use) if (j >= 1ll * w[i] * use) dp[j] = max(dp[j], dp[j - w[i] * use] + 1ll * v[i] * use); cout << dp[s]; exit(0); } void sub45() { vector <vector <pii>> lst; lst.resize(s + 1); for (int i = 1; i <= n; ++i) { k[i] = min(k[i], s / w[i]); lst[w[i]].eb(v[i], k[i]); } vector <pii> best; for (int i = 1; i <= s; ++i) { sort(lst.rbegin(), lst.rend()); ll need = s / i; for (auto &[val, cnt] : lst[i]) { cnt = min(cnt, need); int use = 1; for (; use <= cnt; use <<= 1) { best.eb(val * use, i * use); cnt -= use; need -= use; } if (need && cnt) { best.eb(val * cnt, i * cnt); need -= cnt; cnt = 0; } } } vector <ll> dp(s + 1, 0); for (auto &[val, weight] : best) for (int j = s; j >= weight; --j) dp[j] = max(dp[j], dp[j - weight] + val); cout << dp[s]; exit(0); } int main() { if (ifstream(task".inp")) nx fast cin >> s >> n; for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i] >> k[i], mxk = max(mxk, k[i]); // if (n == 1) return cout << 1ll * v[1] * min(s / w[1], k[1]), 0; // if (n <= 100 && mxk <= 10) sub23(); sub45(); }

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:7:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:68:31: note: in expansion of macro 'nx'
   68 |     if (ifstream(task".inp")) nx
      |                               ^~
knapsack.cpp:7:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define nx freopen (task".inp","r",stdin), freopen (task".out","w",stdout);
      |                                            ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:68:31: note: in expansion of macro 'nx'
   68 |     if (ifstream(task".inp")) nx
      |                               ^~
#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...