Submission #1059471

#TimeUsernameProblemLanguageResultExecution timeMemory
1059471vjudge1Knapsack (NOI18_knapsack)C++14
73 / 100
1061 ms20312 KiB
/* Discord: powder7854 https://www.facebook.com/hai290605 https://codeforces.com/profile/Etohari https://oj.vnoi.info/user/powder */ #include "bits/stdc++.h" #include "ext/pb_ds/assoc_container.hpp" #include "ext/pb_ds/tree_policy.hpp" //@Etohari using namespace std; using namespace __gnu_pbds; template < class T, class G > bool minimum(T& a, const G b) { return b < a ? a = b, 1 : 0; } template < class T, class G > bool maximum(T& a, const G b) { return a < b ? a = b, 1 : 0; } template < class T > using heap_min = priority_queue < T, vector < T >, greater < T > >; template < class T > using heap_max = priority_queue < T, vector < T >, less < T > >; template < class T > using ordered_set = tree < T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update >; template < class T > using ordered_multiset = tree < T, null_type, less_equal < T >, rb_tree_tag, tree_order_statistics_node_update >; #define my_wife "Thu" #define bit(mask,i) ((mask>>i)&1) #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define __lcm(a,b) ((int64_t)(a) / __gcd((a), (b)) * (b)) #define rand(l, r) uniform_int_distribution < int64_t > (l, r)(rng) mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int32_t MOD = 1e9 + 7; constexpr int32_t MAXN = 1e6 + 10; constexpr int32_t MAXM = 1e6 + 10; constexpr int32_t INF32 = 0x3f3f3f3f; constexpr int64_t INF64 = 0x3f3f3f3f3f3f3f3f; constexpr int16_t DR[] = { }; constexpr int16_t DC[] = { }; int n, s, cnt, v[MAXN], w[MAXN], k[MAXN]; int64_t dp[MAXN]; pair < int, int > bag[4 * MAXN]; signed main() { cin.tie(nullptr)->sync_with_stdio(false); cin >> s >> n; for (int i = 1; i <= n; i ++) { cin >> v[i] >> w[i] >> k[i]; } for (int i = 1; i <= n; i ++) { for (int j = 1; j <= k[i] && 1LL * j * w[i] <= s; j *= 2) { bag[++ cnt] = {j * v[i], j * w[i]}; k[i] -= j; } if (k[i] && 1LL * k[i] * w[i] <= s) { bag[++ cnt] = {k[i] * v[i], k[i] * w[i]}; } } for (int i = 1; i <= cnt; i ++) { const auto& [v, w] = bag[i]; for (int j = s; j >= w; j --) { dp[j] = max(dp[j - w] + v, dp[j]); } } cout << dp[s]; return (0 ^ 0); } /* Cho tới khi nào ? */

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:65:29: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |                 const auto& [v, w] = bag[i];
      |                             ^
#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...