Submission #516701

#	Time	Username	Problem	Language	Result	Execution time	Memory
516701		rodov	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	147 ms	77204 KiB

skyscraper

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80