fork(1) download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<cstring>
  4.  
  5. #define max1 10000
  6.  
  7. using namespace std;
  8.  
  9. struct node
  10. {
  11. 	int fee, fun;
  12. };
  13.  
  14.  
  15. int max(int x, int y)
  16. {
  17. 	return x>y?x:y;
  18. }
  19.  
  20.  
  21. int a[2][max1];
  22. node dp[max1];
  23. int p, n;
  24.  
  25.  
  26. node solve(int pos, int cur)
  27. {	
  28. 	if(dp[pos].fee!=0 || dp[pos].fun!=0)
  29. 	{
  30. 		return dp[pos];
  31. 	}
  32.  
  33. 	if(pos == n)
  34. 	{
  35. 		return dp[pos] = (node){cur, 0};
  36. 	}
  37.  
  38. 	if(cur+a[0][pos]<=p)
  39. 	{
  40. 		node l = solve(pos+1, cur+a[0][pos]);
  41. 		node r = solve(pos+1, cur);
  42.  
  43. 		if(l.fun + a[1][pos] > r.fun)
  44. 		{
  45. 			return dp[pos] = (node){l.fee, l.fun + a[1][pos]};
  46. 		}
  47.  
  48. 		else
  49. 		{
  50. 			return dp[pos] = (node){r.fee, r.fun};
  51. 		}		
  52. 	}
  53.  
  54. 	if(cur+a[0][pos]>p)
  55. 	{
  56. 		return dp[pos] = solve(pos+1, cur);
  57. 	}
  58.  
  59. 	//else 
  60. 	return dp[pos] = (node){cur, 0};
  61. }
  62.  
  63.  
  64. int main()
  65. {
  66. 	freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_PARTY.txt", "r", stdin);
  67.  
  68. 	while(1)
  69. 	{
  70. 		scanf("%d %d", &p, &n);
  71.  
  72. 		if(p==0 && n==0)
  73. 		break;
  74.  
  75. 		for(int i=0; i<n; i++)
  76. 		{
  77. 			dp[i].fee = 0;
  78. 			dp[i].fun = 0;
  79.  
  80. 			scanf("%d %d", &a[0][i], &a[1][i]);
  81. 		}
  82.  
  83. 		node ans = solve(0, 0);
  84.  
  85. 		printf("%d %d\n", ans.fee, ans.fun);
  86. 	}
  87. }
Success #stdin #stdout 0s 15392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JG1Bu0
language:
C++ (gcc 8.3)
created:
7 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!