fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int MAXN = 1e5 + 5;
  5.  
  6.  
  7. int s, n, dp[MAXN];
  8. vector<pair<int, int>> wei[MAXN];
  9. signed main(){
  10.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11.     freopen("B4.inp", "r", stdin);
  12.     freopen("B4.out", "w", stdout);
  13.     cin >> s >> n;
  14.     for(int i = 1; i <= n; ++i){
  15.         int v, w, k;
  16.         cin >> v >> w >> k;
  17.         if(w > s) continue;
  18.         wei[w].push_back({v, k});
  19.     }
  20.  
  21.     for(int i = 1; i <= s; ++i){
  22.         dp[i] = -1e9;
  23.     }
  24.     dp[0] = 0;
  25.  
  26.     for(int w = 1; w <= s; ++w){
  27.         sort(wei[w].begin(), wei[w].end(), greater<>());
  28.     }
  29.  
  30.     for(int w = 1; w <= s; ++w){
  31.         if(wei[w].empty()) continue;
  32.  
  33.         vector<int> items;
  34.         int limit = s / w;
  35.         for(auto [val, cnt] : wei[w]){
  36.             int take = min(cnt, limit);
  37.             limit -= take;
  38.             while(take--) items.push_back(val);
  39.             if(limit == 0) break;
  40.         }
  41.  
  42.         for(int v : items){
  43.             for(int i = s; i >= w; --i){
  44.                 if(dp[i - w] != -1e9){
  45.                     dp[i] = max(dp[i], dp[i - w] + v);
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     int res = 0;
  52.     for(int i = 1; i <= s; ++i){
  53.         res = max(res, dp[i]);
  54.     }
  55.     cout << res;
  56.  
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 6120KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0zRgCO
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!