fork download 
  1. #include <limits>
  2. #include <limits>
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. #define int   long long
  6. #define dl '\n'
  7. const int INF = 1e18;
  8. #define printvec(v) for(int i=0;i<v.size();i++){cout<<v[i]<<" ";}cout<<endl;
  9. #define loop(i,n){} for(int i=0;i<n;i++){}
  10. #define read(v,n)   for(int i=0;i<n;i++){cin>>v[i];}
  11. #define all(v)                ((v).begin()), ((v).end())
  12. #define rall(v)                ((v).rbegin()), ((v).rend())
  13. typedef vector<int> vi;
  14. typedef vector<pair<int,int>> vip;
  15. #define ll long long
  16. void Antoine_Sobhy(){
  17.   ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  18. #ifndef ONLINE_JUDGE
  19.   // freopen("business.in", "r", stdin);
  20.   freopen("/home/antoine/Desktop/acpc/input.txt", "r", stdin);
  21.   freopen("/home/antoine/Desktop/acpc/output.txt", "w", stdout);
  22. #endif
  23. }
  24. const int N=15;
  25. int dp[N+1][1<<N];
  26. int dp2[N+1][1<<N];
  27. int n;
  28. vi a(N);
  29. int mx=0;
  30. int ans=0;
  31. int rec(int last,int mask){
  32.   if (__builtin_popcount(mask)==n)
  33.   {
  34.     return n*2;
  35.   }
  36.  
  37.   int &ret=dp[last][mask];
  38.   if (~ret)return ret;
  39.   ret=0;
  40.   if (__builtin_popcount(mask)==0 )
  41.   {
  42.     for (int i=0;i<n;i++)
  43.     {
  44.       if ( (mask& (1ll<<i) )==0)
  45.       {
  46.          ret=max(rec(i,mask|1ll<<i)+a[i],ret);
  47.       }
  48.     }
  49.   }
  50.   else if (__builtin_popcount(mask)==(n-1))
  51.   {
  52.     for (int i=0;i<n;i++)
  53.     {
  54.       if ( (mask& (1ll<<i) )==0)
  55.       {
  56.         ret=max(rec(i,mask|1ll<<i)+a[i]+abs(a[i]-a[last]),ret);
  57.       }
  58.     }
  59.  
  60.   }
  61.   else
  62.   {
  63.     for (int i=0;i<n;i++)
  64.     {
  65.       if ( (mask& (1ll<<i) )==0)
  66.       {
  67.         ret=max(rec(i,mask|1ll<<i)+abs(a[i]-a[last]),ret);
  68.       }
  69.     }
  70.   }
  71.  
  72.   return ret;
  73.  
  74. }
  75.  
  76. int freq(int last,int mask){
  77.   if(__builtin_popcount(mask)==n)
  78.   {
  79.     return 1;
  80.   }
  81.  
  82.   int &ret=dp2[last][mask];
  83.   if (~ret)return ret;
  84.   int opt=rec(last,mask);
  85.   if (__builtin_popcount(mask)==0 )
  86.   {
  87.     for (int i=0;i<n;i++)
  88.     {
  89.       if ( (mask& (1ll<<i) )==0)
  90.       {
  91.         if (opt==rec(i,mask|1ll<<i)+a[i] )
  92.         {
  93.           ret+=freq(i,mask|(1ll<<i));
  94.         }
  95.       }
  96.     }
  97.   }
  98.   else if (__builtin_popcount(mask)==(n-1))
  99.   {
  100.     for (int i=0;i<n;i++)
  101.     {
  102.       if ( (mask& (1ll<<i) )==0)
  103.       {
  104.         if (opt==rec(i,mask|1ll<<i)+a[i]+abs(a[i]-a[last]) )
  105.         {
  106.           ret+=freq(i,mask|(1ll<<i));
  107.         }
  108.       }
  109.     }
  110.  
  111.   }
  112.   else
  113.   {
  114.     for (int i=0;i<n;i++)
  115.     {
  116.       if ( (mask& (1ll<<i) )==0)
  117.       {
  118.         if (opt==rec(i,mask|1ll<<i)+abs(a[i]-a[last]) )
  119.         {
  120.           ret+=freq(i,mask|(1ll<<i));
  121.         }
  122.       }
  123.     }
  124.   }
  125.   return ret;
  126.  
  127. }
  128.  
  129. void solve(){
  130.  
  131.   mx=0;
  132.   ans=0;
  133.   a.resize(n);
  134.   read(a,n);
  135.   memset(dp,-1,sizeof dp);
  136.   mx=rec(0,0);
  137.   memset(dp,-1,sizeof dp2);
  138.   freq(0,0);
  139.   cout<<mx<<" "<<ans<<dl;
  140.  
  141. }
  142.  
  143. int32_t main(){
  144.   Antoine_Sobhy();
  145.   int t=1;
  146.   // cin>>t;
  147.   // int tc=0;
  148.   while(true) {
  149.     cin>>n;
  150.     if (n==0)return 0;
  151.     // cout<<"Case "<<++tc<<":"<<endl;
  152.     solve();
  153.   }
  154.  
  155.   return 0;
  156.  
  157. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/EvmmQh
language:
C++14 (gcc 8.3)
created:
5 days 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!