#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 101;
const ll MAXL = 2001;
const ll MOD = 1e9+7;
ll n, l;
ll heights[MAXN];
ll dp[MAXN][MAXN][MAXL][2][2]; // number of elems, number of cc, value if all other things are next value, left occupied, right occupied
#define fin cin
void gen_case() {
set<int> chosen;
srand(time(0));
ofstream fout("skyscraper.in");
int curn = 8;
int curl = 1000;
fout << curn << " " << curl << "\n";
for (int i = 0; i < curn; i++) {
int v;
do v = rand() % 1001;
while (chosen.find(v) != chosen.end());
chosen.insert(v);
if (i) fout << " ";
fout << v;
}
fout << endl;
fout.close();
}
/*
Transitions:
We can create a new cc, add to an existing one, or merge two
New cc:
Rescale all cc boundaries to the next increment
open spaces = cc-1
current value = 2*next-cur elem
this could go in any of the open spaces
*/
void dpa(ll &a, ll &b) {
a += b;
a %= MOD;
}
// void dpa(ll &a, ll &b) {
// a += b;
// a %= MOD;
// }
bool valid(vector<int> &v) {
int s = 0;
for (int i = 0; i < v.size()-1; i++) s += abs(heights[v[i+1]-1]-heights[v[i]-1]);
return (s <= l);
}
int bash() {
vector<int> v(n);
iota(v.begin(), v.end(), 1);
bool worked = 1;
int ans = 0;
while (worked) {
if (valid(v)) ans++;
worked = next_permutation(v.begin(), v.end());
}
return ans;
}
int solve() {
//memset(dp, 0, sizeof(dp));
//ifstream fin("skyscraper.in");
ios_base::sync_with_stdio(false); fin.tie(NULL);
fin >> n >> l;
for (ll i = 0; i < n; i++) fin >> heights[i];
sort(heights, heights+n);
ll curv = 2*(heights[1]-heights[0]);;
if (curv <= l) dp[1][1][curv][0][0] = 1;
curv += heights[0]-heights[1];
if (curv <= l) {
dp[1][1][curv][1][0] = 1;
dp[1][1][curv][0][1] = 1;
}
heights[n] = heights[n-1];
for (ll i = 2; i <= n; i++) {
for (ll j = 1; j <= min(i, n+1-i); j++) {
for (ll v = 0; v <= l; v++) {
for (ll lo = 0; lo < 2; lo++) {
for (ll ro = 0; ro < 2; ro++) {
if (j > 1) {
ll bounds = 2*(j-1)-lo-ro;
ll ex = (heights[i]-heights[i-1])*bounds+2*heights[i]-2*heights[i-1];
if (ex <= v) {
ll cur = (ll) (j-lo-ro)*dp[i-1][j-1][v-ex][lo][ro];
cur %= MOD;
dpa(dp[i][j][v][lo][ro], cur);
}
ll nex = ex;
if (nex <= v) {
if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][0][ro]);
if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j-1][v-nex][lo][0]);
}
}
ll bounds = 2*j-lo-ro;
ll ex = (heights[i]-heights[i-1])*bounds;
if (ex <= v) {
ll cur = (ll) (2*j-lo-ro)*dp[i-1][j][v-ex][lo][ro];
cur %= MOD;
dpa(dp[i][j][v][lo][ro], cur);
}
ll nex = ex;
if (nex <= v) {
if (lo) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][0][ro]);
if (ro) dpa(dp[i][j][v][lo][ro], dp[i-1][j][v-nex][lo][0]);
}
bounds = 2*j-lo-ro;
ex = (heights[i]-heights[i-1])*bounds;
if (ex <= v) {
ll cur = (ll) (j)*dp[i-1][j+1][v-ex][lo][ro];
cur %= MOD;
dpa(dp[i][j][v][lo][ro], cur);
}
}
}
}
}
}
ll ans = 0;
for (ll i = 0; i <= l; i++) {
dpa(ans, dp[n][1][i][1][1]);
}
//fin.close();
return ans;
}
int main() {
int s = solve();
int b = bash();
assert(s == b);
cout << s << "\n";
return 0;
while (1) {
gen_case();
int s = solve();
int b = bash();
if (s != b) {
cerr << s << " " << b << endl;
}
assert(s == b);
}
}
Compilation message
skyscraper.cpp: In function 'bool valid(std::vector<int>&)':
skyscraper.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for (int i = 0; i < v.size()-1; i++) s += abs(heights[v[i+1]-1]-heights[v[i]-1]);
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2068 ms |
596 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
