fork(1) download 
  1. #include <iostream>
  2. #include <vector>
  3. #include<string.h>
  4. using namespace std;
  5.  
  6. int main() {
  7. 	// your code goes here
  8. 	const int MAX_MONEY=10001;
  9. 	vector<int> calories;
  10. 	vector<int> moneys;
  11. 	vector<int> nos;
  12. 	vector<int> types;
  13. 	int n,d,no,d2,d3;
  14. 	int dp[MAX_MONEY],dp2[MAX_MONEY],dp3[MAX_MONEY];
  15. 	int up;
  16. 	memset(dp,-1,sizeof(dp));
  17. 	memset(dp2,-1,sizeof(dp2));
  18. 	memset(dp3,-1,sizeof(dp3));
  19. 	cin>>up;
  20. 	cin>>n;
  21. 	for(int i=0;i<n;i++){
  22. 		cin>>d>>no>>d2>>d3;
  23. 		types.push_back(d);
  24. 		nos.push_back(no);
  25. 		moneys.push_back(d2);
  26. 		calories.push_back(d3);
  27. 	}
  28. 	dp2[0]=0;
  29. 	for(int k=0;k<2;k++){
  30. 		for(int i=(k==0?0:300);i<up;i++){
  31. 			if(dp2[i]==-1)continue;
  32. 			for(int j=0;j<moneys.size();j++){
  33. 				if(types[j]!=k)continue;
  34. 				if(i+moneys[j]>up)continue;
  35. 				d2=i+moneys[j];
  36. 				d3=dp2[i]+calories[j];
  37. 				if(dp2[d2]<d3){
  38. 					dp2[d2]=d3;
  39. 					dp[d2]=nos[j];
  40. 				}
  41. 			}
  42. 		}
  43. 	}
  44. 	memset(dp2,-1,sizeof(dp2));
  45. 	memset(dp3,-1,sizeof(dp3));
  46. 	for(int i=up;i>0;i--){
  47. 		if(dp[i]==-1){
  48. 			continue;
  49. 		}
  50. 		d=(dp2[i]==-1?0:dp2[i])+calories[dp[i]];
  51. 		d2=i-moneys[dp[i]];
  52. 		if(dp2[d2]<d){
  53. 			dp2[d2]=d;
  54. 			dp3[d2]=nos[dp[i]];
  55. 		}
  56. 	}
  57. 	int p=0,c=0;
  58. 	cout<<"最高カロリーになるメニューは\n";
  59. 	while(dp3[p]!=-1){
  60. 		cout<<dp3[p]<<"番のメニュー ";
  61. 		p=p+moneys[dp3[p]];
  62. 	}
  63.  
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4304KB
comments (?)
stdin 
5000
35
0	0	327	248
0	1	356	314
0	2	179	226
0	3	173	47
0	4	288	108
0	5	132	120
0	6	206	149
0	7	421	72
0	8	206	301
0	9	394	415
0	10	459	480
0	11	152	223
0	12	112	100
0	13	173	284
0	14	167	85
0	15	125	399
0	16	114	187
0	17	223	474
1	18	176	376
1	19	104	200
1	20	472	333
1	21	357	19
1	22	194	199
1	23	465	387
1	24	447	146
1	25	302	376
1	26	311	410
1	27	193	490
1	28	116	124
1	29	489	407
1	30	121	309
1	31	321	466
1	32	400	316
1	33	164	27
1	34	102	364
stdout 
最高カロリーになるメニューは
15番のメニュー 15番のメニュー 15番のメニュー 15番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー 34番のメニュー
https://ideone.com/S6yVEr
language:
C++ (gcc 8.3)
created:
5 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!