fork(37) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int,int> ii;
  7. typedef vector<int> vi;
  8. typedef vector<ii> vii;
  9. typedef long double ld;
  10.  
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define mp make_pair
  15.  
  16. ll dp[101][101][1001][3]; 
  17. /*
  18. dp[i][j][k][l] : 
  19. i - number of numbers placed
  20. j - number of connected components
  21. k - total sum currently (filling empty spaces with a_{i} (0-indexed)
  22. l - number of endpoints that are filled
  23. */
  24. ll a[101];
  25. const ll MOD = 1e9 + 7;
  26.  
  27. int main()
  28. {
  29. 	ios_base::sync_with_stdio(0); cin.tie(0);
  30. 	int n, l;
  31. 	cin>>n>>l;
  32. 	for(int i = 0; i < n; i++)
  33. 	{
  34. 		cin>>a[i];
  35. 	}
  36. 	sort(a, a + n);
  37. 	if(n == 1) //special case
  38. 	{
  39. 		cout << 1;
  40. 		return 0;
  41. 	}
  42. 	a[n] = 10000; //inf for simplicity
  43. 	if(a[1] - a[0] <= l) dp[1][1][a[1] - a[0]][1] = 2; //fill a[0] at one of the endpoints, there are 2 endpoints to fill.
  44. 	if(2*(a[1] - a[0]) <= l) dp[1][1][2*(a[1] - a[0])][0] = 1; //fill a[0] in the middle, positions doesn't matter.
  45.  
  46. 	for(int i = 1; i < n; i++)
  47. 	{
  48. 		int diff = a[i + 1] - a[i]; //this thing is "INF" if i = n - 1.
  49. 		for(int j = 1; j <= i; j++)
  50. 		{
  51. 			for(int k = 0; k <= l; k++)
  52. 			{
  53. 				for(int z = 0; z < 3; z++)
  54. 				{
  55. 					if(!dp[i][j][k][z]) continue; //this value does not exist
  56. 					//First, we try to fill one of the ends
  57. 					if(z < 2 && k + diff*(2*j - z - 1) <= l) //there are 2*j - z - 1 positions that we're supposed to "upgrade" (-1 because one of the positions is merged with the endpoints after this move)
  58. 					{
  59. 						if(i == n - 1)
  60. 						{
  61. 							dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] = (dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] + dp[i][j][k][z]*(2-z)*j)%MOD; //we have j con. comp. to choose to merge with
  62. 						}
  63. 						else if(z == 0 || j > 1) //otherwise this coincides with i == n - 1
  64. 						{
  65. 							dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] = (dp[i + 1][j][k + diff*(2*j - z - 1)][z + 1] + dp[i][j][k][z]*(2-z)*(j-z))%MOD; //can only merge with the con comp. that are not connected to ends.
  66. 						}
  67. 						if(k + diff*(2*j - z + 1) <= l) //now we create a new cc.
  68. 						{
  69. 							dp[i + 1][j + 1][k + diff*(2*j - z + 1)][z + 1] = (dp[i + 1][j + 1][k + diff*(2*j - z + 1)][z + 1] + dp[i][j][k][z]*(2-z))%MOD; //we can choose one of the ends to create
  70. 						}
  71. 					}
  72. 					//Next, we dont fill the ends. 
  73. 					//Part 1 : Create new cc
  74. 					if(k + diff*(2*j - z + 2) <= l) //2 new positions to "upgrade"
  75. 					{
  76. 						dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z] = (dp[i + 1][j + 1][k + diff*(2*j - z + 2)][z] + dp[i][j][k][z])%MOD; //nothing new happens
  77. 					}
  78. 					//Part 2 : Stick to one cc
  79. 					if(k + diff*(2*j - z) <= l) //no new positions to "upgrade"
  80. 					{
  81. 						dp[i + 1][j][k + diff*(2*j - z)][z] = (dp[i + 1][j][k + diff*(2*j - z)][z] + dp[i][j][k][z]*(2*j - z))%MOD; //we can merge in 2*j - z possible positions
  82. 					}
  83. 					//Part 3 : Merge two ccs together
  84. 					if((k + diff*(2*j - z - 2) <= l) && (j >= 2) && (i == n - 1 || j > 2 || z < 2))
  85. 					{
  86. 						if(z == 0)
  87. 						{
  88. 							dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*j*(j-1))%MOD; //there are jP2 possible merges
  89. 						}
  90. 						if(z == 1)
  91. 						{
  92. 							dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*(j-1)*(j-1))%MOD; //there are (j-1)P2+(j-1) merges
  93. 						}
  94. 						if(z == 2)
  95. 						{
  96. 							if(i == n - 1)
  97. 							{
  98. 								dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z])%MOD; //there's only 1 place it can go.
  99. 							}
  100. 							else
  101. 							{
  102. 								dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] = (dp[i + 1][j - 1][k + diff*(2*j - z - 2)][z] + dp[i][j][k][z]*(j-2)*(j-1))%MOD; //there're (j-2)P2 + 2(j-2) possiblilities
  103. 							}
  104. 						}
  105. 					}
  106. 				}
  107. 			}
  108. 		}
  109. 	}
  110.  
  111. 	ll answer = 0;
  112. 	for(int i = 0; i <= l; i++)
  113. 	{
  114. 		answer = (answer + dp[n][1][i][2])%MOD; //sum the dp values for all possible sums
  115. 	}
  116. 	cout << answer << '\n';
  117. 	return 0;
  118. }
  119.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.hs:1:2: lexical error at character 'i'
stdout 
Standard output is empty
https://ideone.com/bj9pm9
language:
Haskell (ghc 8.4.4)
created:
8 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!