/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/JOI16_skyscr
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 1007
#define MAXE 100007
bool debug;
ll dp[101][101][1001][3];
/**
we sort the values ai and add them into the permutation one by one.
At each point, we will have some connected components of values
(for example it will be something like 2,?,1,5,?,?,3,?,4)
But then, we can freely arrange each block to form all permutations
dp[i][j][k][l] : number of ways when
i - number of numbers placed
j - number of connected components
k - The "total cost" (assuming that all empty positions contain a[i+1} and a[n+1]=INF). Use this cost is very important.
l - number of endpoints that are filled
For example, {?, ?, 3, ?, 2, 1} would be counted in dp[3][2][5][1]
*/
int a[107];
int N, L;
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> N >> L;
if (N == 1) {
cout << 1 << endl; return 0;
}
for (int i = 1; i <= N; i++) cin >> a[i];
sort(a + 1, a + N + 1);
a[N + 1] = 10000; // INF
dp[0][0][0][0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
for (int k = 0; k <= L; k++) {
for (int m = 0; m <= 2; m++) {
/// imagine that all ? are placed with a[i] (so cost of ? is 0) and now changed to a[i+1]
int cost_diff = (2 * j - m) * (a[i + 1] - a[i]);
if (i + j + 1 - m > N) continue; // number of points > N
if (k - cost_diff < 0) continue; // no initial stage to reach this
/// Case 1: We inserted a[i] to form a new component that doesn't contain an endpoint of the permutation.
dp[i][j][k][m] += dp[i - 1][j - 1][k - cost_diff][m];
/// Case 2: We inserted a[i] to form a new component that contain an endpoint of the permutation.
/// if m==1, the original condition is m=0 so we can put on either side
/// if m==2, the original condition is m=1 which means one end is already occupied and we can only add to one end
if (m==1) dp[i][j][k][m] += 2 * dp[i - 1][j - 1][k - cost_diff][m - 1];
if (m==2) dp[i][j][k][m] += 1 * dp[i - 1][j - 1][k - cost_diff][m - 1];
/// Case 3: We appended a[i] to an existing component such that it doesn't contain an end of the permutation.
/// There were 2j - m component endpoints to choose from : Note that we don't care about the relative orders
/// of the connected components for each DP state since we are considering all permutations
/// (Imagine that they're just free-floating components that we can pluck out of space and join.)
dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - cost_diff][m];
/// Case 4: We appended a[i] to an existing component such that it contains an end of the permutation.
/// This is only possible if m > 0.
/// If m==1, the original stage is m=0, then there were 2j component endpoints to choose from (can append to both sides)
if (m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - cost_diff][m - 1];
/// if m==2, the original state is m=1 meaning 1 end is already occupied so there are j-1 component ends
/// since we can only append to one side
/// (special case is i=N which means j=1)
if (m == 2) {
if (i == N) dp[i][j][k][m] += dp[i - 1][j][k - cost_diff][m - 1];
else if (j > 1) dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - cost_diff][m - 1];
}
/// Case 5: We inserted a[i] to join two existing components. Original state has (j+1) components
/// if m=0, there are j(j+1) ordered pair
if (m==0) {
dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - cost_diff][m];
} else if(m==1) {
/// if m==1, one component is already at the end and you can not move it, there are j*j ordered pair
dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - cost_diff][m];
} else {
/// If m==2, there were j(j - 1) ordered pairs of components to choose from
/// unless i=N, where you just join 2 component to form a complete line
if (i == N) dp[i][j][k][m] += dp[i - 1][j + 1][k - cost_diff][m];
else dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - cost_diff][m];
}
dp[i][j][k][m] %= MOD;
}
}
}
}
ll ans = 0;
for (int i = 0; i <= L; i++) ans += dp[N][1][i][2];
cout << ans % MOD << endl;
if(debug) cout << endl << "EOL" << endl;
}
/*
4 10
3 6 2 9
8 35
3 7 1 5 10 2 11 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
716 KB |
Output is correct |
| 6 |
Correct |
1 ms |
716 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
716 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
588 KB |
Output is correct |
| 3 |
Correct |
1 ms |
588 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
1 ms |
588 KB |
Output is correct |
| 6 |
Correct |
1 ms |
588 KB |
Output is correct |
| 7 |
Correct |
1 ms |
588 KB |
Output is correct |
| 8 |
Correct |
1 ms |
588 KB |
Output is correct |
| 9 |
Correct |
1 ms |
588 KB |
Output is correct |
| 10 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
1 ms |
332 KB |
Output is correct |
| 5 |
Correct |
2 ms |
716 KB |
Output is correct |
| 6 |
Correct |
1 ms |
716 KB |
Output is correct |
| 7 |
Correct |
1 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
460 KB |
Output is correct |
| 9 |
Correct |
1 ms |
716 KB |
Output is correct |
| 10 |
Correct |
1 ms |
460 KB |
Output is correct |
| 11 |
Correct |
1 ms |
588 KB |
Output is correct |
| 12 |
Correct |
1 ms |
588 KB |
Output is correct |
| 13 |
Correct |
1 ms |
588 KB |
Output is correct |
| 14 |
Correct |
1 ms |
588 KB |
Output is correct |
| 15 |
Correct |
1 ms |
588 KB |
Output is correct |
| 16 |
Correct |
1 ms |
588 KB |
Output is correct |
| 17 |
Correct |
1 ms |
588 KB |
Output is correct |
| 18 |
Correct |
1 ms |
588 KB |
Output is correct |
| 19 |
Correct |
1 ms |
588 KB |
Output is correct |
| 20 |
Correct |
1 ms |
588 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2380 KB |
Output is correct |
| 22 |
Correct |
64 ms |
35724 KB |
Output is correct |
| 23 |
Correct |
94 ms |
47384 KB |
Output is correct |
| 24 |
Correct |
85 ms |
46788 KB |
Output is correct |
| 25 |
Correct |
96 ms |
50500 KB |
Output is correct |
| 26 |
Correct |
84 ms |
45964 KB |
Output is correct |
| 27 |
Correct |
34 ms |
23492 KB |
Output is correct |
| 28 |
Correct |
42 ms |
26832 KB |
Output is correct |
| 29 |
Correct |
69 ms |
41148 KB |
Output is correct |
| 30 |
Correct |
98 ms |
50788 KB |
Output is correct |
