Submission #1190308

#TimeUsernameProblemLanguageResultExecution timeMemory
1190308laplace_daemoniumKnapsack (NOI18_knapsack)C++20
73 / 100
1095 ms1864 KiB
#include <iostream> #include <fstream> #include <vector> #include <cmath> #include <unordered_map> #include <map> #include <unordered_set> #include <set> #include <queue> #include <assert.h> #include <deque> #include <stack> #include <bitset> #include <cassert> #include <cstddef> #include <algorithm> #include <numeric> #include <list> #define ll long long int #define ld long double #define pii pair<int, int> #define pll pair<ll, ll> #define ppii pair<pair<int, int>, int> #define MOD 998'244'353 #define MOD1 1'000'000'007 #define YES { cout << "YES\n"; return; } #define NO { cout << "NO\n"; return; } #define what_is(x) cerr << #x << " is " << x << endl; #define bit(x) cout << bitset<64>(x) << "\n" #define inf 1e9 #define INF 1e18 #define CUBE(x) (x*x*x) using namespace std; void solve() { int s, n; cin >> s >> n; vector<int> w(n+1); vector<ll> v(n+1); vector<int> k(n+1); for (int i = 1; i <= n; i++) { cin >> v[i]; cin >> w[i]; cin >> k[i]; } vector<ll> dp(2001); for (int i = 1; i <= n; i++) { for (int sum = s; sum >= w[i]; sum--) { for (int j = 1; j*w[i] <= sum && j <= k[i]; j++) { dp[sum] = max(dp[sum-j*w[i]] + j*v[i], dp[sum]); } } } cout << dp[s] << "\n"; } int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; //cin >> tt; while (tt--) 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...