Submission #516701

#TimeUsernameProblemLanguageResultExecution timeMemory
516701rodovSkyscraper (JOI16_skyscraper)C++14
100 / 100
147 ms77204 KiB
#include <bits/stdc++.h>

using namespace std;

long long n,L,res,diff;
long long d[107][107][1007][3];
long long a[107];
const long long MOD = 1e9+7;

int main() {
    cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(n==1) { cout << 1 << endl; return 0; }
    a[n+1]=10000;
    sort(a+1, a+1+n);
    d[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++) {
                    diff = (2*j-m)*(a[i+1]-a[i]);
                    if(k-diff<0) continue;
                    d[i][j][k][m] += (d[i-1][j+1][k-diff][m] * j)%MOD;
                    d[i][j][k][m] += (d[i-1][j-1][k-diff][m] * (j-m)) %MOD;
                    d[i][j][k][m] += (d[i-1][j][k-diff][m] * (2*j-m))%MOD;
                    if(m>0) d[i][j][k][m] += (d[i-1][j-1][k-diff][m-1] * (3-m))%MOD;
                    if(m>0) d[i][j][k][m] += (d[i-1][j][k-diff][m-1] *(3-m) )%MOD;

                    d[i][j][k][m] %= MOD;
                }
    res = 0;
    for(int k=0; k<=L; k++) res += d[n][1][k][2];
    res %= MOD;
    cout << res << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...