fork download
copy 
  1. #include<cstdio>
  2. #include<iostream>
  3. #include<cstring>
  4. #define INF 1000000000
  5. using namespace std;
  6. int k,n,m;
  7. long long dp[51][150][51][51],mm[51][150][51];
  8. int c[51],v[51],pr=-1;
  9. long long solve(int k,int B,int prev,int cnt)
  10. {
  11. 	if(B<0)return -INF;
  12. 	if(B==0 and k>0)return -INF;
  13. 	if(k==0)return 0;
  14. 	if(dp[k][B][prev][cnt]!=-1)return dp[k][B][prev][cnt];
  15. 	long long ans=-INF,idx=-1;
  16. 	for(int i=0;i<n;i++)
  17. 	{
  18. 		if(prev!=i)
  19. 		{
  20. 			int tmp=solve(k-1,B-c[i],i,1);
  21. 			if(tmp!=-INF)
  22. 			{
  23. 				if(tmp+v[i]>ans)
  24. 				{
  25. 				ans=tmp+v[i];
  26. 				idx=i;
  27. 				}
  28. 				else if(tmp+v[i]==ans)
  29. 				{
  30. 					if((v[i]-c[i])>(v[idx]-c[idx]))
  31. 					idx=i;
  32. 				}
  33. 			}
  34. 		}
  35. 		else
  36. 		{
  37. 			int val=v[i]/2;
  38. 			if(cnt>1)val=0;
  39. 			int tmp=solve(k-1,B-c[i],i,cnt+1);
  40. 			if(tmp!=-INF)
  41. 			{
  42. 				if(tmp+val>ans)
  43. 				{
  44. 				ans=tmp+val;
  45. 				idx=i;
  46. 				}
  47. 			}
  48. 		}
  49. 	}
  50. 	mm[k][B][prev]=idx;
  51. 	pr=idx;
  52. 	return dp[k][B][prev][cnt]=ans;
  53. }
  54. void recurse(int k,int B,int pre)
  55. {
  56.     if(k==0)return;
  57.     else
  58.     {
  59.         int x=mm[k][B][pre];
  60.         recurse(k-1,B-c[x],x);
  61.          cout<<x+1<<" ";
  62.     }
  63. }
  64. int main()
  65. {
  66. 	cin>>k>>n>>m;
  67. 	while(k|n|m)
  68. 	{
  69. 		memset(dp,-1,sizeof dp);
  70. 		memset(mm,-1,sizeof mm);
  71. 		long long ans=-INF;
  72. 		for(int i=0;i<n;i++)
  73. 		{
  74. 			cin>>c[i]>>v[i];
  75. 			v[i]<<=1;
  76. 		}
  77. 		double x=solve(k,m,-1,0);
  78. 		if(x<=0)
  79. 		cout<<"0.0"<<endl;
  80. 		else
  81. 		{
  82. 			printf("%.1lf\n",x/2);
  83.             recurse(k-1,m-c[pr],pr);
  84.             cout<<pr+1;
  85.     }
  86.     cout<<endl;
  87. 		cin>>k>>n>>m;
  88. 	}
  89. }
Success #stdin #stdout 0.17s 161216KB
comments (?)
stdin
copy 
2 1 5
3 5
3 5 20
2 5
18 6
1 1
3 3
2 3
0 0 0
stdout
copy 
0.0

13.0
1 5 1
https://ideone.com/mJanLS
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!