Submission #1147215

#TimeUsernameProblemLanguageResultExecution timeMemory
1147215lidplfKnapsack (NOI18_knapsack)C++20
73 / 100
338 ms327680 KiB
#include <bits/stdc++.h> #define pii pair<int,int> #define pb push_back #define yes "YES" #define no "NO" #define ll long long #define MOD 1000000007 #define all(x) x.begin(),x.end() #define MOD2 998244353 using namespace std; void solve(int cas){ ll s,n; cin>>s>>n; vector<vector<ll>> nums(s+1); for (int i = 0; i < n; i++){ ll v,w,k; cin>>v>>w>>k; for (int j = 0; j < min(s, k); j++){ nums[w].emplace_back(v); } } for (int i = 0; i <= s; i++){ sort(nums[i].rbegin(), nums[i].rend()); } ll dp[s+2][s+1]; memset(dp, 0, sizeof dp); for (int i = s; i >= 0; i--){ for (int weight = 0; weight <= s; weight++){ dp[i][weight] = dp[i+1][weight]; int p = 0; ll sm = weight, add = 0; while (p < nums[i].size() && sm <= s){ sm += i; add += nums[i][p]; p++; if (sm <= s){ dp[i][weight] = max(dp[i][weight], add + dp[i+1][sm]); } } } } cout << dp[1][0] << '\n'; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin>>t; for (int i = 1; i <= t; i++){ solve(i); } 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...