rendered paste body#include <iostream.h>struct good{ long profit,mass,max;};struct entry{ long val; int* count;};int n;struct good* arr;struct entry* bag;void copy(int* x,int* y){ for(int i = 0;i < n;i++) y[i] = x[i];}long findans(int a,int b){ int i = 0,j,profit,mass,m; bag = new entry[b+1]; for(i = 0;i <= b;i++){ bag[i].count = new int[n]; for(j = 0;j < n;j++) bag[i].count[j] = 0; } //for each item for(i = 0;i < n;i++){ if(arr[i].mass > b) continue; mass = arr[i].mass; profit = arr[i].profit; for(j = 0;j < arr[i].max;j++){ for(m = b;m >= 0;m--) if(bag[m].val && m+mass <= b && bag[m+mass].val < (bag[m].val + profit)){ bag[m+mass].val = bag[m].val + profit; copy(bag[m].count,bag[m+mass].count); bag[m+mass].count[i]++; } if(bag[mass].val < profit){ for(int x = 0;x < n;x++) bag[mass].count[x] = 0; bag[mass].val = profit; bag[mass].count[i]++; } /*for(int x = 0;x <= b;x++) cout << "\n" << x << " " << bag[x] << " " << prev[x] << " " << ind[x]; cout << "\n";*/ } } //cout << "\n-------------------------BAG ARRAY-----------------------"; long max = -1; int maxind = -1; for(i = b;i >= a;i--) if(bag[i].val && max < bag[i].val) max = bag[i].val,maxind = i; return maxind; }int main(){ int i = 0,a,b; long ans = 0; cin >> n >> a >> b; arr = new good[n]; for(i = 0;i < n;i++) cin >> arr[i].profit >> arr[i].mass >> arr[i].max; ans = findans(a,b); if(ans == -1){ cout << "-1"; return 0; } cout << bag[ans].val; for(i = 0;i < n;i++) cout << "\n" << bag[ans].count[i]; return 0;}