Submission #1212497

#TimeUsernameProblemLanguageResultExecution timeMemory
1212497cubedKnapsack (NOI18_knapsack)C++20
0 / 100
152 ms327680 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define yes cout<<"YES\n" #define no cout<<"NO\n" #define endl '\n' const int MOD = 1e9+7; const int inf =1e9; bool multi=false; int max_t=1000; int f(int i, int s, vector<pair<int, int>> &a, vector<vector<int>> &dp) { if (i==0) { if (s>=a[i].second) return a[i].first; else return 0; } if (dp[i][s]!=-1) return dp[i][s]; int take=a[i].first+f(i-1, s-a[i].second, a, dp); int notake=f(i-1, s,a, dp); return dp[i][s]=max(take, notake); } int main() { ll t=1; if (multi) cin>>t; while (t--) { int s, n; cin>>s>>n; vector<vector<int>> a(n, vector<int>(3)); for (int i=0; i<n; i++) { int v,w,k; cin>>v>>w>>k; a[i][0]=v; a[i][1]=w; a[i][2]=k; } vector<pair<int, int>> items; for (auto i:a) { int times=i[2]; for (int j=0; j<times; j++) { items.push_back({i[0], i[1]}); } } vector<vector<int>> dp(items.size(), vector<int>(s+1, -1)); cout<<f(a.size()-1, s, items, dp); } 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...