fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. struct stone {
  4. 	int s;
  5. 	int e;
  6. 	int l;
  7. } stones[104];
  8. bool cmp(stone x, stone y){
  9. 	if(x.l == 0)
  10. 		return false;
  11. 	if(y.l == 0)
  12. 		return true;
  13. 	return 1.0*x.s/x.l<1.0*y.s/y.l;
  14. }
  15. int n;
  16. int dp[104][10004];
  17. int knapsack(int item, int time){
  18. 	if(item == n)	return 0;
  19. 	int& ret = dp[item][time];
  20. 	if(ret != -1)	return ret;
  21. 	ret = max(knapsack(item+1,time),
  22. 			stones[item].e-stones[item].l*time+knapsack(item+1,time+stones[item].s));
  23. 	return ret;
  24. }
  25. int solve(){
  26. 	cin>>n;
  27. 	int t;
  28. 	for(int i = 0 ; i < n;i++){
  29. 		cin>>stones[i].s;
  30. 		cin>>stones[i].e;
  31. 		cin>>stones[i].l;
  32. 	}
  33. 	sort(stones,stones+n,cmp);
  34. 	memset(dp, -1, sizeof(dp));
  35. 	return knapsack(0,0);
  36. }
  37.  
  38. int main() {
  39. 	int TC;
  40. 	cin>>TC;
  41. 	for(int i = 1;i<=TC;i++)
  42. 		cout<<"Case #"<<i<<": "<<solve()<<'\n';;
  43.  
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 19304KB
comments (?)
stdin
copy 
3
4
20 10 1
5 30 5
100 30 1
5 80 60
3
10 4 1000
10 3 1000
10 8 1000
2
12 300 50
5 200 0
stdout
copy 
Case #1: 105
Case #2: 8
Case #3: 500
https://ideone.com/FHyofG
language:
C++14 (gcc 8.3)
created:
4 years 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!