Submission #445513

#	Time	Username	Problem	Language	Result	Execution time	Memory
445513		KYoA_A	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	252 ms	120772 KiB

skyscraper

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define kyoa_a
#define rep(i, a, b)	for(int i = a; i < (b); ++i)
#define rrep(a, b, c)	for(int a = (b); a > c; --a)
#define each(a, b)	for(auto& a : b)

#define sz(x)       (int)(x).size()
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(), (a).rend()

#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define vt vector
#define ar array
#define pii pair<int, int>
#define vi vector<int>
#define pll pair<ll, ll>
#define pct(x) __builtin_popcount(x)
#define fbo(x) find_by_order(x)
#define ook(x) order_of_key(x)
#define rsz resize
#define bk back()

constexpr int log2(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x))
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <class T> bool umin(T& a, const T& b){return b<a?a=b, 1:0;}
template <class T> bool umax(T& a, const T& b){return a<b?a=b, 1:0;}

using ll = long long;
using ld = long double;
using str = string;

const int inf = (int)1e9 + 5;
const ll infl = (ll)1e18 + 5;
const int mod = 1e9 + 7;
const int N = 101;

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

/*---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---XXX---*/

const int MOD=1000000007;
struct Mint {
    int val;
 
    Mint(long long v = 0) {
        if (v < 0)
            v = v % MOD + MOD;
        if (v >= MOD)
            v %= MOD;
        val = v;
    }
 
    static int mod_inv(int a, int m = MOD) {
        int g = m, r = a, x = 0, y = 1;
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        } 
        return x < 0 ? x + m : x;
    } 
    explicit operator int() const {
        return val;
    }
    Mint& operator+=(const Mint &other) {
        val += other.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    Mint& operator-=(const Mint &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
    static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
           #if !defined(_WIN32) || defined(_WIN64)
                return x % m;
           #endif
           unsigned x_high = x >> 32, x_low = (unsigned) x;
           unsigned quot, rem;
           asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (m));
           return rem;
    }
    Mint& operator*=(const Mint &other) {
        val = fast_mod((uint64_t) val * other.val);
        return *this;
    }
    Mint& operator/=(const Mint &other) {
        return *this *= other.inv();
    }
    friend Mint operator+(const Mint &a, const Mint &b) { return Mint(a) += b; }
    friend Mint operator-(const Mint &a, const Mint &b) { return Mint(a) -= b; }
    friend Mint operator*(const Mint &a, const Mint &b) { return Mint(a) *= b; }
    friend Mint operator/(const Mint &a, const Mint &b) { return Mint(a) /= b; }
    Mint& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
    Mint& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
    Mint operator++(int32_t) { Mint before = *this; ++*this; return before; }
    Mint operator--(int32_t) { Mint before = *this; --*this; return before; }
    Mint operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
    bool operator==(const Mint &other) const { return val == other.val; }
    bool operator!=(const Mint &other) const { return val != other.val; }
    Mint inv() const {
        return mod_inv(val);
    }
    Mint power(long long p) const {
        assert(p >= 0);
        Mint a = *this, result = 1;
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            a *= a;
            p >>= 1;
        }
        return result;
    }
    friend ostream& operator << (ostream &stream, const Mint &m) {
        return stream << m.val;
    }
    friend istream& operator >> (istream &stream, Mint &m) {
        return stream>>m.val;   
    }
};


Mint dp[N][N][1005][3];
int n, L, a[N];

void solve(){
	cin >> n >> L;


	rep(i, 1, n+1) cin >> a[i];
	if(n == 1){cout << 1 << '\n'; return;}
	sort(a+1, a+n+1);

	dp[0][0][0][0] = 1;
	rep(i, 1, n+1) rep(j, 1, i+1) rep(l, 0, 1001){
		int nl = l - (a[i] - a[i-1])*2*(j - 1);
		if(nl >= 0){
			dp[i][j][l][0] += dp[i-1][j-1][nl][0]*j;
			dp[i][j][l][1] += dp[i-1][j-1][nl][0]*2;
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][0] += dp[i-1][j][nl][0]*2*j;
				dp[i][j][l][1] += dp[i-1][j][nl][0]*2;
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][0] += dp[i-1][j+1][nl][0]*(j);
				}
				nl += 2*(a[i] - a[i-1]);
			}
			nl += 2*(a[i] - a[i-1]);
		}
		nl += (a[i] - a[i-1]);
		if(nl >= 0){
			dp[i][j][l][1] += dp[i-1][j-1][nl][1]*(j-1);
			dp[i][j][l][2] += dp[i-1][j-1][nl][1];
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][1] += dp[i-1][j][nl][1]*(2*j - 1);
				dp[i][j][l][2] += dp[i-1][j][nl][1];
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][1] += dp[i-1][j+1][nl][1]*(j);

				}
				nl += 2*(a[i] - a[i-1]);
			}
			nl += 2*(a[i] - a[i-1]);
		}
		nl += a[i] - a[i-1];
		if(nl >= 0){
			dp[i][j][l][2] += dp[i-1][j-1][nl][2]*max(0, j-2);
			nl -= 2*(a[i] - a[i-1]);
			if(nl >= 0){
				dp[i][j][l][2] += dp[i-1][j][nl][2]*(2*(j-1));
				nl -= 2*(a[i] - a[i-1]);
				if(nl >= 0){
					dp[i][j][l][2] += dp[i-1][j+1][nl][2]*j;
				}
			}
		}
	}

	Mint ans = 0;
	rep(l, 0, L+1) ans += dp[n][1][l][2];
	cout << ans << '\n';
}


int main(){
	#ifdef kyoa_a
		auto begin = std::chrono::high_resolution_clock::now();
	#endif

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
		solve();

	#ifdef kyoa_a
		auto end = std::chrono::high_resolution_clock::now();
		cout << setprecision(3) << fixed;
		cout << "Execution time: " << std::chrono::duration_cast<std::chrono::duration<double>>(end - begin).count() << " seconds" << endl;
	#endif
}

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