fork(2) download
copy 
  1.  
  2. #include <bits/stdc++.h>
  3. #define mod 1000000007ll
  4. #define mod2 100000009ll
  5. #define mod3 998244353
  6. #define pb push_back
  7. #define fastIO ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  8. #define readi(x) scanf("%d",&x)
  9. #define reads(x)  scanf("%s", x)
  10. #define readl(x) scanf("%I64d",&x)
  11. #define PI 3.141592653589793238462643383
  12. #define repi(i,a,b) for(int i=a;i<b;i++)
  13. #define repd(i,a,b) for(int i=a;i>b;i--)
  14. #define mp make_pair
  15. #define ll long long
  16. #define sorti(a,b) sort(a,b)
  17. #define sortd(a,b,tp) sort(a,b,greater<tp>())
  18. #define fi first
  19. #define se second
  20.  
  21. using namespace std;
  22. typedef pair<int,int> pii;
  23. typedef pair<ll,ll> pll;
  24. typedef pair<long double,long double>pdd;
  25. template<class T>
  26. using max_pq = priority_queue<T>;
  27. template<class T>
  28. using min_pq = priority_queue<T,vector<T>,greater<T>>;
  29. int oo = 0x3f3f3f3f;
  30.  
  31. int n;
  32. ll arr[20],freqCache[16][1<<16],cache[16][1<<16];
  33.  
  34. ll dp(int prev,int mask)
  35. {
  36. 	if(mask==(1<<n)-1)
  37. 	{
  38. 		freqCache[prev][mask]=1;
  39. 		return arr[prev];
  40. 	}
  41.  
  42. 	if(cache[prev][mask]!=-1)
  43. 	{
  44. 		return cache[prev][mask];
  45. 	}
  46.  
  47. 	ll ans=0;
  48. 	for(int i=1;i<=n;i++)
  49. 	{
  50. 		if(!(mask&(1<<(i-1))))
  51. 		{
  52. 			ll val=dp(i,mask|(1<<(i-1)));
  53. 			if(prev==0)
  54. 			{
  55. 				val+=arr[i];
  56. 			}
  57. 			else{
  58. 				val+=abs(arr[prev]-arr[i]);
  59. 			}
  60. 			if(val>ans)
  61. 			{
  62. 				freqCache[prev][mask]=freqCache[i][mask|(1<<(i-1))];
  63. 				ans=val;
  64. 			}
  65. 			else if(val==ans){
  66. 				freqCache[prev][mask]+=freqCache[i][mask|(1<<(i-1))];
  67. 			}
  68. 		}
  69. 	}
  70. 	cache[prev][mask]=ans;
  71. 	return ans;
  72. }
  73.  
  74. class Histogram {
  75. public:
  76. 	void solve(istream& cin, ostream& cout) {
  77. 		while(1)
  78. 		{
  79. 			cin>>n;
  80. 			if(!n)
  81. 				break;
  82. 			memset(cache,-1, sizeof(cache));
  83. 			memset(freqCache,0, sizeof(cache));
  84. 			repi(i,1,n+1)
  85. 			{
  86. 				cin>>arr[i];
  87. 			}
  88.  
  89. 			cout<<(dp(0,0)+(ll)2*n)<<" "<<freqCache[0][0]<<"\n";
  90. 		}
  91. 	}
  92. };
  93.  
  94. int main() {
  95.     fastIO;
  96. 	Histogram solver;
  97. 	std::istream& in(std::cin);
  98. 	std::ostream& out(std::cout);
  99. 	solver.solve(in, out);
  100. 	return 0;
  101. }
  102.  
Success #stdin #stdout 0s 31624KB
comments (?)
stdin
copy 
4
1 2 3 4
3
2 6 5
0
stdout
copy 
20 0
24 0
https://ideone.com/EfLq4a
language:
C++14 (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!