# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
866840 | prohacker | Skyscraper (JOI16_skyscraper) | C++14 | 1 ms | 860 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N = 105;
const int INF = INT_MAX;
const int mod = 1e9+7;
int n,lim,dp[N][N][1010][3],a[N];
int ans;
void add(int &x, const int y) {
x += y;
if(x >= mod) {
x -= mod;
}
}
signed main()
{
if (fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> lim;
if(n == 1) {
cout << 0;
return 0;
}
for(int i = 1 ; i <= n ; i++) {
cin >> a[i];
}
sort(a+1,a+n+1);
a[n+1] = 100010;
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 <= lim ; k++) {
for(int m = 0 ; m <= 2 ; m++) {
int delta = (2*j-m)*(a[i+1]-a[i]);
if(delta > k) {
continue;
}
add(dp[i][j][k][m],dp[i-1][j-1][k-delta][m]);
add(dp[i][j][k][m],1LL*(2*j-m)*dp[i-1][j][k-delta][m]%mod);
if(m > 0) {
if(j > 0) {
add(dp[i][j][k][m],1LL*(3-m)*dp[i-1][j-1][k-delta][m-1]%mod);
}
if(m == 1) {
add(dp[i][j][k][m],1LL*2*j*dp[i-1][j][k-delta][m-1]%mod);
}
else {
if(i == n) {
add(dp[i][j][k][m],dp[i-1][j][k-delta][m-1]);
}
else {
if(j > 0) {
add(dp[i][j][k][m],1LL*(j-1)*dp[i-1][j][k-delta][m-1]%mod);
}
}
}
}
if(m == 2) {
if(i == n) {
add(dp[i][j][k][m],dp[i-1][j+1][k-delta][m]);
}
else {
add(dp[i][j][k][m],1LL*j*(j-1)*dp[i-1][j+1][k-delta][m]%mod);
}
}
else if(m == 1) {
add(dp[i][j][k][m],1LL*j*j*dp[i-1][j+1][k-delta][m]%mod);
}
else {
add(dp[i][j][k][m],1LL*j*(j+1)*dp[i-1][j+1][k-delta][m]%mod);
}
}
}
}
}
for(int i = 0 ; i <= lim ; i++) {
add(ans,dp[n][1][i][2]);
}
cout << ans;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |