Submission #1171501

#TimeUsernameProblemLanguageResultExecution timeMemory
1171501abcsedafaefKnapsack (NOI18_knapsack)C++20
0 / 100
1095 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), c(n), t(n); for (int i = 0; i < n; i++) { cin >> v[i]; } for (int i = 0; i < n; i++) { cin >> c[i]; } for (int i = 0; i < n; i++) { cin >> t[i]; } // dp[i][j] = maximum value using items i to n-1 with budget j. vector<vector<int>> dp(n + 1, vector<int>(x + 1, 0)); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j <= x; j++) { int skip = dp[i + 1][j]; dp[i][j] = skip; for (int k = 1; k <= t[i]; k++) { if (j - k * c[i] >= 0) { int pick = k * v[i] + dp[i + 1][j - k * c[i]]; dp[i][j] = max(dp[i][j], pick); } } } } 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...