Submission #1171503

#TimeUsernameProblemLanguageResultExecution timeMemory
1171503abcsedafaefKnapsack (NOI18_knapsack)C++20
0 / 100
1097 ms8256 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define str string #define vi vector<int> #define vll vector<long long> #define vc vector<char> #define vs vector<string> #define pi pair<int, int> #define vpi vector<pi> #define vvi vector<vector<int>> #define si set<int> #define ins insert #define pb(a) push_back(a) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define rep(i, b) for (int i = 0; i < (b); i++) #define fast_io \ ios_base::sync_with_stdio(false); \ std::cin.tie(NULL) #define coutyes cout << "YES" << endl; #define coutno cout << "NO" << endl; using namespace std; ll N = 1000000; vll primes; vll v(N, 1); void sieve() { v[0] = 0; v[1] = 0; ll maxN = N; for (int i = 2; i * i <= maxN; i++) { if (v[i] == 1) { for (int j = i * i; j <= maxN; j += i) v[j] = 0; } } for (int i = 2; i <= maxN; i++) { if (v[i] != 0) { primes.pb(i); } } } ll mod = 1e9 + 7; vector<ll> fact, invFact; ll power(ll x, ll y) { ll res = 1; x = x % mod; while (y > 0) { if (y & 1) res = (res * x) % mod; y = y >> 1; x = (x * x) % mod; } return res; } void precom(int N) { fact.resize(N + 1); invFact.resize(N + 1); fact[0] = 1; for (int i = 1; i <= N; i++) { fact[i] = (fact[i - 1] * i) % mod; } invFact[N] = power(fact[N], mod - 2); for (int i = N - 1; i >= 0; i--) { invFact[i] = (invFact[i + 1] * (i + 1)) % mod; } } ll ncrmod(ll n, ll r) { if (r > n) return 0; return (((fact[n] * invFact[r]) % mod) * invFact[n - r]) % mod; } bool isPrime(ll n) { if (n <= 1) return false; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) return false; } return true; } void solve() { int x, n; cin >> x >> n; vi v(n), w(n), t(n); for (int i = 0; i < n; i++) { cin >> v[i]; } for (int i = 0; i < n; i++) { cin >> w[i]; } for (int i = 0; i < n; i++) { cin >> t[i]; } // x budget // n items // ith item has // v value , w cost and can be used k times // dp[i][j] represents max value of items we can but from i to n-1 // when budget is j // skip or pick a book // pick -> // 1 -> k>0 a) dp[i][j] = dp[i+1][j-c[i]] // b) dp[i][j] = dp[i+i][j] // 2 -> k=0 a) dp[i][j] = dp[i+1][j] // skip -> dp[i][j] = dp[i+1][j] // dp[n - 1][0] = 0; vector<vector<int>> dp(n + 1, vector<int>(x + 1, 0)); for (int i = n - 1; i >= 0; i--) { for (int j = x; j >= 0; j--) { int pick = 0, skip = dp[i + 1][j]; for (int k = 1; k <= t[i]; k++) { if (j - (k * w[i]) >= 0) { pick = k * v[i] + dp[i + 1][j - (k * w[i])]; dp[i][j] = max(pick, skip); } } } } cout << dp[0][x]; } int main() { fast_io; ll t = 1; // cin >> t; while (t--) { solve(); } 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...