Submission #1194209

#TimeUsernameProblemLanguageResultExecution timeMemory
1194209PlayVoltzKnapsack (NOI18_knapsack)C++20
100 / 100
37 ms2884 KiB
#include <bits/stdc++.h> using namespace std; #define ll unsigned long long int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, k, a, b, c; cin>>k>>n; vector <pair<ll, ll> > vect[k+1]; ll dp[k+1]; for (int j=0; j<=k; ++j){ dp[j] = 0; } for (int i=1; i<=n; ++i){ cin>>a>>b>>c; vect[b].push_back(make_pair(a, c)); } for (int i=1; i<=k; ++i){ sort(vect[i].begin(), vect[i].end(), greater<pair<ll, ll> >()); int index = 0; for (int j=0; j<k/i; ++j){ if (index>=vect[i].size())break; for (int l=k; l>=i; --l){ dp[l] = max(dp[l], dp[l-i]+vect[i][index].first); } --vect[i][index].second; if (vect[i][index].second==0)++index; } } cout<<dp[k]; }
#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...