Submission #1147226

#TimeUsernameProblemLanguageResultExecution timeMemory
1147226lidplfKnapsack (NOI18_knapsack)C++20
100 / 100
81 ms66116 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<pair<ll,ll>>> g(s+1); for (int i = 0; i < n; i++){ ll v,w,k; cin>>v>>w>>k; g[w].emplace_back(make_pair(v,k)); } for (int i = 0; i <= s; i++){ sort(g[i].rbegin(), g[i].rend()); } vector<vector<ll>> nums(s+1); for (int i = 0; i <= s; i++){ int p = 0; while (p < g[i].size() && nums[i].size() < s){ while (g[i][p].second > 0 && nums[i].size() < s){ nums[i].emplace_back(g[i][p].first); g[i][p].second--; } p++; } } 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...