fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<cstring>
  4.  
  5. #define max1 102
  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][502];
  23. int p, n;
  24.  
  25.  
  26. node solve(int pos, int cur)
  27. {	
  28. 	if(pos == n)
  29. 	{
  30. 		return (node){cur, 0};
  31. 	}
  32.  	if(dp[pos][cur].fee!=-1)
  33.  		return dp[pos][cur];
  34. 	if(cur+a[0][pos]<=p)
  35. 	{
  36. 		node l = solve(pos+1, cur+a[0][pos]);
  37. 		node r = solve(pos+1, cur);
  38.  
  39. 		if(l.fun + a[1][pos] > r.fun)
  40. 		{
  41. 			return dp[pos][cur] = (node){l.fee, l.fun + a[1][pos]};
  42. 		}
  43.  
  44. 		else if (l.fun + a[1][pos] < r.fun)
  45. 		{
  46. 			return dp[pos][cur] = (node){r.fee, r.fun};
  47. 		}		
  48.  
  49. 		else // if both equal
  50. 			return dp[pos][cur] = (node){min(r.fee,l.fee), r.fun};
  51. 	}
  52.  
  53. 	if(cur+a[0][pos]>p)
  54. 	{
  55. 		return dp[pos][cur] = solve(pos+1, cur);
  56. 	}
  57.  
  58. }
  59.  
  60.  
  61. int main()
  62. {
  63. 	//freopen("C:\\Users\\Shraeyas\\Documents\\pg\\pr_ag\\prag_PARTY.txt", "r", stdin);
  64.  
  65. 	while(1)
  66. 	{
  67. 		for(int i=0;i<max1;i++)
  68. 			for(int j=0;j<501;j++)
  69. 				dp[i][j].fee = dp[i][j].fun = -1;
  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. 			scanf("%d %d", &a[0][i], &a[1][i]);
  78. 		}
  79.  
  80. 		node ans = solve(0, 0);
  81.  
  82. 		printf("%d %d\n", ans.fee, ans.fun);
  83. 	}
  84. }
Success #stdin #stdout 0s 15640KB
comments (?)
stdin
copy 
40 5
12 10
16 10
20 10
24 10
8 3

0 0
stdout
copy 
36 23
https://ideone.com/VO16HX
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!