fork download
copy 
  1. #include <iostream>
  2. #include<cstdio>
  3. #include<string.h>
  4. #include<vector>
  5. using namespace std;
  6. pair<int,int> dp[1200000][20];
  7. int a[20],n;
  8. pair<int,int> f(int mask,int rt)
  9. {
  10.     int i;
  11.     // cout<<mask<<endl;
  12.     if(mask==(1<<n)-1)
  13.     {
  14.         return(make_pair(2*a[rt],1));
  15.     }
  16.     if(dp[mask][rt].first)
  17.     {
  18.         return dp[mask][rt];
  19.     }
  20.     for(i=0; i<n; i++)
  21.     {
  22.         //cout<<(mask&(i<<i));
  23.         if((mask&(1<<i))==0)
  24.         {
  25.             //cout<<1;
  26.             if(a[rt]<a[i])
  27.             {
  28.                 pair<int,int> r = f(mask|(1<<i),i);
  29.                 if(dp[mask][rt].first<r.first)
  30.                 {
  31.                     dp[mask][rt].first=r.first;
  32.                     dp[mask][rt].second=r.second;
  33.                     //dp[mask][rt].second=r.second;
  34.                 }
  35.                 else if(dp[mask][rt].first==r.first) dp[mask][rt].second+=r.second;
  36.             }
  37.             else
  38.             {
  39.                 pair<int,int> r= f(mask|(1<<i),i);
  40.                 if(dp[mask][rt].first<r.first+2*(a[rt]-a[i]))
  41.                 {
  42.                     dp[mask][rt].first=r.first+2*(a[rt]-a[i]);
  43.                     dp[mask][rt].second=r.second;
  44.                 }
  45.                 else if(dp[mask][rt].first==r.first+2*(a[rt]-a[i])) dp[mask][rt].second+=r.second;
  46.             }
  47.         }
  48.     }
  49.  
  50.     return dp[mask][rt];
  51. }
  52. int main()
  53. {
  54.     int ans=0;
  55.     scanf("%d",&n);
  56.     while(n)
  57.     {
  58.         pair<int,int>ans;
  59.         ans=make_pair(0,0);
  60.  
  61.         int i;
  62.         memset(dp,0,sizeof(dp));
  63.         for(i=0; i<n; i++) scanf("%d",&a[i]);
  64.         for(i=0; i<n; i++)
  65.         {
  66.  
  67.             pair<int,int> tm=f(1<<i,i);
  68.             if(ans.first<tm.first)
  69.             {
  70.                 ans.first=tm.first;
  71.                 ans.second=tm.second;
  72.             }
  73.             else if(ans.first==tm.first)
  74.             {
  75.                 ans.second+=tm.second;
  76.             }
  77.         }
  78.  
  79.         printf("%d %d\n",2*n+ans.first,ans.second);
  80.         scanf("%d",&n);
  81.     }
  82.     return 0;
  83. }
  84.  
  85.  
Success #stdin #stdout 0.2s 190784KB
comments (?)
stdin
copy 
4
1 2 3 4
0
stdout
copy 
20 8
https://ideone.com/vnLa8S
language:
C++ (gcc 8.3)
created:
10 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!