#include <bits/stdc++.h>
using namespace std;
template <class T> int size(const T &x) { return x.size(); }
#define rep(i,a,b) for (__typeof(a) i=(a); i<(b); ++i)
#define iter(it,c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
const int INF = 2147483647;
int arr[1010];
int n, l;
int mem[110][1010][2][110][2];
int mod = 1000000007;
ll dp(int at, int curl, int kl, int k, int kr) {
// kl = 1 if there is a segment connected to the left border, 0 otherwise
// kr = 1 if there is a segment connected to the right border, 0 otherwise
// k is the number of segments in the middle
int nxtl = curl;
if (at > 0) {
// add the penalty from the last element:
nxtl += (kl+kr+2*k)*abs(arr[at]-arr[at-1]);
}
if (nxtl > l) return 0;
if (k < 0) return 0;
if (at == n-1) {
return k == 0 ? 1 : 0;
}
if (mem[at][curl][kl][k][kr] != -1)
return mem[at][curl][kl][k][kr];
ll res = 0;
res += dp(at+1, nxtl, 1, k, kr); // connect to left segment
res += dp(at+1, nxtl, 1, k-1, kr)*k; // connect to left segment, and join to some middle segment
res += dp(at+1, nxtl, kl, k, 1); // connect to right segment
res += dp(at+1, nxtl, kl, k-1, 1)*k; // connect to right segment, and join to some middle segment
res += dp(at+1, nxtl, kl, k+1, kr); // new segment
res += dp(at+1, nxtl, kl, k, kr)*k*2; // connect to some middle segment
res += dp(at+1, nxtl, kl, k-1, kr)*k*(k-1); // join two middle segments
return mem[at][curl][kl][k][kr] = res % mod;
}
int main() {
memset(mem,-1,sizeof(mem));
cin >> n >> l;
rep(i,0,n) cin >> arr[i];
sort(arr,arr+n);
cout << dp(0, 0, 0, 0, 0) << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
191608 KB |
Output is correct |
| 2 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 3 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 4 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 5 |
Correct |
99 ms |
191612 KB |
Output is correct |
| 6 |
Correct |
98 ms |
191608 KB |
Output is correct |
| 7 |
Correct |
97 ms |
191612 KB |
Output is correct |
| 8 |
Correct |
99 ms |
191692 KB |
Output is correct |
| 9 |
Correct |
97 ms |
191720 KB |
Output is correct |
| 10 |
Correct |
98 ms |
191608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
99 ms |
191652 KB |
Output is correct |
| 2 |
Correct |
103 ms |
191608 KB |
Output is correct |
| 3 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 4 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 5 |
Correct |
95 ms |
191608 KB |
Output is correct |
| 6 |
Correct |
99 ms |
191736 KB |
Output is correct |
| 7 |
Correct |
103 ms |
191608 KB |
Output is correct |
| 8 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 9 |
Correct |
102 ms |
191608 KB |
Output is correct |
| 10 |
Correct |
100 ms |
191608 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
191608 KB |
Output is correct |
| 2 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 3 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 4 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 5 |
Correct |
99 ms |
191612 KB |
Output is correct |
| 6 |
Correct |
98 ms |
191608 KB |
Output is correct |
| 7 |
Correct |
97 ms |
191612 KB |
Output is correct |
| 8 |
Correct |
99 ms |
191692 KB |
Output is correct |
| 9 |
Correct |
97 ms |
191720 KB |
Output is correct |
| 10 |
Correct |
98 ms |
191608 KB |
Output is correct |
| 11 |
Correct |
99 ms |
191652 KB |
Output is correct |
| 12 |
Correct |
103 ms |
191608 KB |
Output is correct |
| 13 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 14 |
Correct |
99 ms |
191608 KB |
Output is correct |
| 15 |
Correct |
95 ms |
191608 KB |
Output is correct |
| 16 |
Correct |
99 ms |
191736 KB |
Output is correct |
| 17 |
Correct |
103 ms |
191608 KB |
Output is correct |
| 18 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 19 |
Correct |
102 ms |
191608 KB |
Output is correct |
| 20 |
Correct |
100 ms |
191608 KB |
Output is correct |
| 21 |
Correct |
98 ms |
191736 KB |
Output is correct |
| 22 |
Correct |
324 ms |
191612 KB |
Output is correct |
| 23 |
Correct |
361 ms |
191608 KB |
Output is correct |
| 24 |
Correct |
316 ms |
191608 KB |
Output is correct |
| 25 |
Correct |
359 ms |
191736 KB |
Output is correct |
| 26 |
Correct |
307 ms |
191736 KB |
Output is correct |
| 27 |
Correct |
155 ms |
191608 KB |
Output is correct |
| 28 |
Correct |
179 ms |
191608 KB |
Output is correct |
| 29 |
Correct |
281 ms |
191736 KB |
Output is correct |
| 30 |
Correct |
358 ms |
191736 KB |
Output is correct |
