fork(1) download
copy 
  1.  
  2.     #include <cstdio>
  3.     #include <cstring>
  4.     #include <cstdlib>
  5.     using namespace std;
  6.  
  7.     typedef long long i64;
  8.     const int MAX = 16;
  9.  
  10.     int dp[1<<MAX][MAX], a[MAX], n;
  11.     i64 np[1<<MAX][MAX];
  12.  
  13.     int solve(int mask, int idx)
  14.     {
  15.     	if(mask==(1<<n)-1)
  16.     	{
  17.     		np[mask][idx] = 1;
  18.     		return a[idx];
  19.     	}
  20.     	int &ret = dp[mask][idx];
  21.     	if(ret != -1) return ret;
  22.     	ret = 0;
  23.     	for(int i = 0, val; i < n; i++)
  24.     	{
  25.     		if(!(mask & (1 << i)))
  26.     		{
  27.     			val = solve(mask | (1 << i), i) + abs(a[i]-a[idx]);
  28.     			if(val > ret)
  29.     			{
  30.     				ret = val;
  31.     				np[mask][idx] = 0;
  32.     			}
  33.     			if(val==ret) np[mask][idx] += np[mask | (1 << i)][i];
  34.     		}
  35.     	}
  36.     	return ret;
  37.     }
  38.  
  39.     int main()
  40.     {
  41.     	int i, val, maxval;
  42.     	i64 cnt;
  43.     	while(scanf("%d", &n)==1 && n)
  44.     	{
  45.     		for(i = 0; i < n; i++) scanf("%d", &a[i]);
  46.     		maxval = 0;
  47.     		memset(dp, -1, sizeof dp);
  48.     		for(i = 0; i < n; i++)
  49.     		{
  50.     			val = solve(1<<i, i) + a[i];
  51.     			if(val > maxval)
  52.     			{
  53.     				maxval = val;
  54.     				cnt = 0;
  55.     			}
  56.     			if(val==maxval) cnt += np[1<<i][i];
  57.     		}
  58.     		maxval += (n << 1);
  59.     		printf("%d %lld\n", maxval, cnt);
  60.     	}
  61.     	return 0;
  62.     }
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/TbSIwB
language:
C++14 (gcc 8.3)
created:
7 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!