제출 #471823

#제출 시각아이디문제언어결과실행 시간메모리
471823CodeChamp_SSKnapsack (NOI18_knapsack)C++17
0 / 100
116 ms262148 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define sz(v) (int)v.size() #define ps(y) cout << fixed << setprecision(y) #define ms(arr, v) memset(arr, v, sizeof(arr)) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define trav(x, v) for(auto &x: v) #define w(t) int t; cin >> t; while(t--) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = a; i >= b; i--) #define rep0(i, n) rep(i, 0, n - 1) #define rrep0(i, n) rrep(i, n - 1, 0) #define rep1(i, n) rep(i, 1, n) #define rrep1(i, n) rrep(i, n, 1) #define inp(arr, n) rep0(i, n) cin >> arr[i]; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<bool> vb; typedef vector<string> vs; typedef map<ll, ll> mii; typedef map<char, ll> mci; typedef priority_queue<ll> pq_mx; typedef priority_queue<ll, vi, greater<>> pq_mn; typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds; /* * find_by_order(i) -> returns an iterator to the element at ith position (0 based) * order_of_key(i) -> returns the position of element i (0 based) */ const int N = 1e5 + 5, M = 2e3 + 5; const int mod = 1e9 + 7; //const int mod = 998244353; const ll inf = 1e18; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fio() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); } int n, s, Vi[N], wi[N], ki[N]; ll dp[N][M]; ll f(int i, int j) { if (i == n) return 0; if (dp[i][j] != -1) return dp[i][j]; ll ans = 0; for (ll x = 0; x <= ki[i] and j + x * wi[i] <= s; x++) ans = max(ans, x * Vi[i] + f(i + 1, j + x * wi[i])); return dp[i][j] = ans; } int main() { fio(); cin >> s >> n; rep0(x, n) cin >> Vi[x] >> wi[x] >> ki[x]; ms(dp, -1); cout << f(0, 0); 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...