#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define ll long long
#define maxn 102
#define maxl 1010
int N, L;
int nums[maxn];
int dp[2][2][maxn][maxn][maxl];
//above should be initialized to all zeroes
int mult(ll a, ll b) {
return (a*b)%mod;
}
//how do i get here
int go(int lflag, int rflag, int ind, int groups, int curl) {
bool isz = lflag == 0 && rflag == 0 && ind == 0 && groups == 0 && curl == L; //solely for debugging
//flags for wether left or right are filled
// the index of the thing we are placing
// the number of groups that there are
int numopen = groups + 1; //one on the end
if (groups < 0) return 0;
if (lflag) numopen--;
if (rflag) numopen--;
// if (numopen == 0) cout << "here: " << ind << endl;
//every open spot increases by the difference in values because of the increase
int numdec = numopen*2; //number to decrease
if (!lflag) numdec--; //don't sub on the left
if (!rflag) numdec--;
if (ind > 0) {
//every open spot was considered before to be nums[ind-1], but now it is considered to be nums[ind]
curl -= (nums[ind]-nums[ind-1]) * numdec;
}
if (lflag < 0 || lflag > 1) return 0;
if (rflag < 0 || rflag > 1) return 0;
if (numopen < 0) return 0; //should not happen
if (curl < 0) return 0;
// if (numopen == 0) cout << "here: " << ind << endl;
if (ind == N) {
//already placed everything
// cout << "at N with numopen equal to " << numopen << endl;
if (lflag && rflag && numopen == 0) {
return 1;
} //nothing should be open at the end
else return 0; //did not satisfy the correct conditions
}
if (dp[lflag][rflag][ind][groups][curl] != -1) {
return dp[lflag][rflag][ind][groups][curl];
}
int res = 0; //this is the result
//option 1 : add it loosely wherever
res += mult(numopen, go(lflag, rflag, ind+1, groups+1, curl));
res %= mod;
//increase the number of groups by 1, you can put it in any of the open portions
// if (isz) cout << "from option 1: " << res << " : " << numopen << endl;
//option 2 : loosely place me on the left edge (or right edge) - adds a group
if (!lflag) res += go(lflag+1, rflag, ind+1, groups+1, curl);
res %= mod;
if (!rflag) res += go(lflag, rflag+1, ind+1, groups+1, curl);
res %= mod;
//option 3 : bind me to one thing (must have a group to do this)
// you can actually bind me to either side if I am in the middle
int numbind = 2*numopen;
if (!rflag) numbind--;
if (!lflag) numbind--;
if (groups >= 1) res += mult(numbind, go(lflag, rflag, ind+1, groups, curl));
res %= mod;
//option 4 : bind me to something and put me on the edge (need to have a group for this)
if (groups >= 1 && !lflag) res += go(lflag+1, rflag, ind+1, groups, curl);
res %= mod;
if (groups >= 1 && !rflag) res += go(lflag, rflag+1, ind+1, groups, curl);
res %= mod;
//option 5: double bind me (subtracts 1 from the number of groups);
//must bind be in the middle of two things
numbind = numopen;
if (!lflag) numbind--;
if (!rflag) numbind--;
if (groups >= 2) res += mult(numbind, go(lflag, rflag, ind+1, groups-1, curl));
res %= mod;
return dp[lflag][rflag][ind][groups][curl] = res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> L;
if (N == 1) {
cout << 1 << endl;
return 0; //just in case
}
for (int i = 0; i < N; i++) {
cin >> nums[i];
}
sort(nums, nums+N);
for (int i1 = 0; i1 < 2; i1++) { //set everything to negative one
for (int i2 = 0; i2 < 2; i2++) {
for (int i3 = 0; i3 < maxn; i3++) {
for (int i4 = 0; i4 < maxn; i4++) {
for (int i5 = 0; i5 < maxl; i5++) {
dp[i1][i2][i3][i4][i5] = -1;
}
}
}
}
}
int ans = go(0, 0, 0, 0, L); //starting state
cout << ans << endl;
//debug below
// for (int i1 = 0; i1 < 2; i1++) { //set everything to negative one
// for (int i2 = 0; i2 < 2; i2++) {
// for (int i3 = 0; i3 < 4; i3++) {
// for (int i4 = 0; i4 <= 4; i4++) {
// for (int i5 = 0; i5 <= L; i5++) {
// // if (dp[i1][i2][i3][i4][i5] != -1)
// // cout << i1 << " " << i2 << " " << i3 << " " << i4 << " " << i5 << ": " << dp[i1][i2][i3][i4][i5] << endl;
// }
// }
// }
// }
// }
cin >> ans;
}
//dp state
//number we are one (going to be 0 through N)
// ---- also dictates how many numbers are added
//number of things that are loosely placed
// ----- dictates number of spots
// flags for if either end is set (2 of them)
// current sum of cost (going up to L)
// 2 * 2 * N * N * L = 40,000,000 states
// transitions:
// loosely place me (creates two open spots)
// loosely place me on an edge (creates one open spot)
// place me on edge and bind me to another guy (subtracts one open)
// bind me in the middle to one guy (keeps open spots constant)
// bind two middle guys together
// bind something on the edge and something in the middle
//issue is with cost recalculation (if loosely placed cost is -2 * my value)
//every time, each open spot is assumed to be just the current value
//when we move up a number, we subtract (nums[i] - nums[i-1]) * # open spots
//transitions are still o(1) but bad
//handle case for n = 1 explicitly (left and right stuff gets weird)
Compilation message
skyscraper.cpp: In function 'int go(int, int, int, int, int)':
skyscraper.cpp:20:7: warning: unused variable 'isz' [-Wunused-variable]
bool isz = lflag == 0 && rflag == 0 && ind == 0 && groups == 0 && curl == L; //solely for debugging
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
127 ms |
164980 KB |
Output is correct |
| 3 |
Correct |
128 ms |
165076 KB |
Output is correct |
| 4 |
Correct |
130 ms |
165096 KB |
Output is correct |
| 5 |
Correct |
126 ms |
165240 KB |
Output is correct |
| 6 |
Correct |
129 ms |
165240 KB |
Output is correct |
| 7 |
Correct |
132 ms |
165240 KB |
Output is correct |
| 8 |
Correct |
152 ms |
165240 KB |
Output is correct |
| 9 |
Correct |
129 ms |
165240 KB |
Output is correct |
| 10 |
Correct |
126 ms |
165240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
165240 KB |
Output is correct |
| 2 |
Correct |
133 ms |
165240 KB |
Output is correct |
| 3 |
Correct |
162 ms |
165240 KB |
Output is correct |
| 4 |
Correct |
128 ms |
165280 KB |
Output is correct |
| 5 |
Correct |
127 ms |
165288 KB |
Output is correct |
| 6 |
Correct |
128 ms |
165288 KB |
Output is correct |
| 7 |
Correct |
129 ms |
165288 KB |
Output is correct |
| 8 |
Correct |
128 ms |
165288 KB |
Output is correct |
| 9 |
Correct |
141 ms |
165288 KB |
Output is correct |
| 10 |
Correct |
135 ms |
165288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
127 ms |
164980 KB |
Output is correct |
| 3 |
Correct |
128 ms |
165076 KB |
Output is correct |
| 4 |
Correct |
130 ms |
165096 KB |
Output is correct |
| 5 |
Correct |
126 ms |
165240 KB |
Output is correct |
| 6 |
Correct |
129 ms |
165240 KB |
Output is correct |
| 7 |
Correct |
132 ms |
165240 KB |
Output is correct |
| 8 |
Correct |
152 ms |
165240 KB |
Output is correct |
| 9 |
Correct |
129 ms |
165240 KB |
Output is correct |
| 10 |
Correct |
126 ms |
165240 KB |
Output is correct |
| 11 |
Correct |
133 ms |
165240 KB |
Output is correct |
| 12 |
Correct |
133 ms |
165240 KB |
Output is correct |
| 13 |
Correct |
162 ms |
165240 KB |
Output is correct |
| 14 |
Correct |
128 ms |
165280 KB |
Output is correct |
| 15 |
Correct |
127 ms |
165288 KB |
Output is correct |
| 16 |
Correct |
128 ms |
165288 KB |
Output is correct |
| 17 |
Correct |
129 ms |
165288 KB |
Output is correct |
| 18 |
Correct |
128 ms |
165288 KB |
Output is correct |
| 19 |
Correct |
141 ms |
165288 KB |
Output is correct |
| 20 |
Correct |
135 ms |
165288 KB |
Output is correct |
| 21 |
Correct |
135 ms |
165288 KB |
Output is correct |
| 22 |
Correct |
521 ms |
165288 KB |
Output is correct |
| 23 |
Correct |
229 ms |
165288 KB |
Output is correct |
| 24 |
Correct |
269 ms |
165288 KB |
Output is correct |
| 25 |
Correct |
298 ms |
165288 KB |
Output is correct |
| 26 |
Correct |
290 ms |
165288 KB |
Output is correct |
| 27 |
Correct |
213 ms |
165352 KB |
Output is correct |
| 28 |
Correct |
267 ms |
165352 KB |
Output is correct |
| 29 |
Correct |
342 ms |
165400 KB |
Output is correct |
| 30 |
Correct |
267 ms |
165400 KB |
Output is correct |
