fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //int tot=0;
  4. pair<int,int> bitmask(int mask,int i,int n,int k,int *height,vector<vector<pair<int,int> > >&dp)
  5. {
  6. 	// cout<<"Entered";
  7. 	if(i>=n){
  8. 	// cout<<"TER";	
  9. 	return make_pair(height[k],1);}
  10. 	// cout<<"TER1";
  11. 	if(((dp[mask][k]).first)!=(-1))
  12. {
  13. 	// cout<<(dp[mask][k]).first;
  14. 	return dp[mask][k];}
  15. 	int maxim=0;
  16. 	int count1=0,count=0;
  17. 	for(int j=0;j<n;j++)
  18. 	{
  19. 		// tot++;
  20. 		// cout<<"LOOP"<<" ";
  21.  
  22. 		if(!(mask&(1<<j)))
  23. 		{
  24. 			// cout<<j<<" ";
  25. 			int temp;
  26. 			count=0;
  27. 			pair<int,int>abc;
  28. 		           	abc=bitmask(mask|(1<<j),i+1,n,j,height,dp);
  29. 			if(i==0)
  30. 			temp=height[j]+abc.first;
  31. 			else temp=abs(height[j]-height[k])+abc.first;
  32. 			count=abc.second;
  33. 			if(maxim<temp)
  34. 			{
  35. 				count1=count;
  36. 				maxim=temp;
  37. 				// if(maxim==0)
  38. 				// cout<<"WRONG"<<" ";
  39. 			}
  40. 			else if(maxim==temp)
  41. 			count1+=count;
  42. 		}
  43. 	}
  44.  
  45. 	dp[mask][k]=make_pair(maxim,count1);
  46. 	return make_pair(maxim,count1);
  47. }
  48. int main() {
  49. 	int n;
  50. 	while(1)
  51. 	{
  52. 		cin>>n;
  53. 		if(n==0)
  54. 		break;
  55. 		vector<vector<pair<int,int> > >dp(1000001,vector<pair<int,int> >(15,make_pair(-1,-1)));
  56. 		// cout<<dp[0][0].first<<endl;
  57. 		int height[n];
  58. 		for(int i=0;i<n;i++)
  59. 		cin>>height[i];
  60. 		int count=0;
  61. 		pair<int,int> abc1=bitmask(0,0,n,1000000,height,dp);
  62. 		int temp1=abc1.first;
  63. 		count=abc1.second;
  64. 		cout<<2*n+temp1<<" "<<count<<endl;
  65. 	}
  66. 	return 0;
  67. }
Success #stdin #stdout 0.12s 151248KB
comments (?)
stdin
copy 
4 4 1 2 3 0
stdout
copy 
20 8
https://ideone.com/Hrv2Fq
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!