fork(1) download
  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
stdin
4
1 2 3 4
3
2 6 5
0
stdout
20 0
24 0