Submission #23499

#	Time	Username	Problem	Language	Result	Execution time	Memory
23499		rubabredwan	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	303 ms	348272 KiB

skyscraper

/* Bismillahir Rahmanir Rahim */

#include <bits/stdc++.h>

using namespace std;

const int N = 105;
const int L = 1005;
const long long mod = 1e9 + 7;

long long dp[N][L][N][2][2];
int n, l, a[N];

long long recur(int at, int sum, int tot, int lf, int rf){
    int fuk = sum + ((a[at] - a[at-1]) * (lf + rf + tot * 2));
    if(fuk > l || tot < 0) return 0;
    if(at == n) return (tot == 0);
    if(dp[at][sum][tot][lf][rf] != -1) return dp[at][sum][tot][lf][rf];

    long long ret = 0;

    ret += recur(at+1, fuk, tot, 1, rf);
    ret += recur(at+1, fuk, tot-1, 1, rf) * tot;
    ret += recur(at+1, fuk, tot, lf, 1);
    ret += recur(at+1, fuk, tot-1, lf, 1) * tot;
    ret += recur(at+1, fuk, tot, lf, rf) * tot * 2;
    ret += recur(at+1, fuk, tot-1, lf, rf) * tot * (tot - 1);
    ret += recur(at+1, fuk, tot+1, lf, rf);

    return dp[at][sum][tot][lf][rf] = ret % mod;
}


int main(){
    cin >> n >> l;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    sort(a+1, a+1+n); a[0] = a[1];
    memset(dp, -1, sizeof(dp));
    cout << recur(1, 0, 0, 0, 0) << endl;
	return 0;
}

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