Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int main()
- {
- while(1)
- {
- int N;
- cin>>N;
- if(N==0)
- return 0;
- long long fact[(1<<N)][N];
- long long count[(1<<N)][N];
- int A[N];
- int i,j,k;
- for(i = 0 ; i< N ; i++)
- cin>>A[i];
- for(i=0 ; i< (1<<N) ; i++)
- for(j=0 ; j< N ; j++)
- count[i][j]=fact[i][j] = 0;
- for (i= 0 ; i<N ; i++)
- {
- count[(1<<i)][i] = 1;
- fact[(1<<i)][i] = 2*A[i]+2;
- }
- for(i= 3 ; i< (1<<N) ; i++)
- {
- for(j = 0 ; j<N ; j++)
- {
- if(i&(1<<j))
- {
- long long int temp_max = 2*A[j]+2;
- long long int c = 0;
- for(k= 0 ; k < N ; k++)
- {
- if(((i - (1<<j))&(1<<k)) != 0)
- {
- if(A[j]<A[k])
- {
- temp_max = max(temp_max,fact[i - (1<<j)][k] +2 );
- }
- else
- {
- temp_max = max(temp_max,fact[i - (1<<j)][k] + 2*abs(A[k]-A[j]) +2 );
- }
- }
- }
- fact[i][j] = temp_max;
- for(k= 0 ; k < N ; k++)
- {
- if(((i - (1<<j))&(1<<k)) != 0)
- {
- if(A[j]<A[k])
- {
- if(fact[i - (1<<j)][k] +2 == temp_max)
- count[i][j] += count[i - (1<<j)][k];
- }
- else
- {
- if(fact[i - (1<<j)][k] + 2*abs(A[k]-A[j]) +2 == temp_max)
- count[i][j] += count[i - (1<<j)][k];
- }
- }
- }
- }
- }
- }
- long long int mm = -1;
- long long int sum = 0;
- long long int tt = mm;
- for(i = 0 ; i< N ; i++)
- {
- mm = max(mm , fact[(1<<N)- 1 ][i] );
- }
- for(i=0;i<N ;i++)
- {
- if(fact[(1<<N)- 1 ][i] == mm)
- sum+= count[(1<<N)- 1 ][i];
- }
- cout<<mm<<" "<<sum<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement