Submission #1143814

#TimeUsernameProblemLanguageResultExecution timeMemory
1143814why1Knapsack (NOI18_knapsack)C++20
100 / 100
38 ms2884 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define pii pair<int,int> #define sz size() #define all(v) v.begin(),v.end() #define fi first #define se second const int N = 3e5; const int mod = 1e9+7; const ll INF = 1e18; const int di[] = {1, -1, 0, 0}; const int dj[] = {0, 0, 1, -1}; void solve() { int n,s; cin>>s>>n; vector<pair<ll,ll>> vec[s+1]; for(int i = 1; i <= n; i++){ ll v,w,k; cin>>v>>w>>k; vec[w].pb({v,k}); } for(int i = 1; i <= s; i++){ sort(vec[i].rbegin(),vec[i].rend()); } ll dp[s+1]; memset(dp,0,sizeof(dp)); for(int i = 1; i <= s; i++){ int cnt=0; for(auto [v,k]: vec[i]){ for(int K = 1; K <= k && K*i <= s; K++){ for(int j = s; j >= i; j--){ dp[j]=max(dp[j],dp[j-i]+v); } } cnt+=k; if(cnt>s/i) break; } } ll ans=0; for(int i = 1; i <= s; i++){ ans=max(ans,dp[i]); } cout<<ans<<"\n"; } int main() { //freopen("cowrun.in","r",stdin); //freopen("cowrun.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t=1; //cin>>t; while(t--) { 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...