제출 #542995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542995		fcw	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	94 ms	2712 KiB

skyscraper

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = int(1e9) + 7;
constexpr int inf = 0x3f3f3f3f;
constexpr int ninf = 0xcfcfcfcf;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
const long double pi = acosl(-1.0);
// Returns -1 if a < b, 0 if a = b and 1 if a > b.
int cmp_double(double a, double b = 0, double eps = 1e-9) {
	return a + eps > b ? b + eps > a ? 0 : 1 : -1;
}
using namespace std;

template<unsigned M_> struct modnum {
    static constexpr unsigned M = M_;
    using ll = long long; using ull = unsigned long long; unsigned x;
    constexpr modnum() : x(0U) {}
    constexpr modnum(unsigned x_) : x(x_ % M) {}
    constexpr modnum(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
    constexpr modnum(ull x_) : x(x_ % M) {}
    constexpr modnum(ll x_) : x(((x_ %= static_cast<ll>(M)) < 0) ? (x_ + static_cast<ll>(M)) : x_) {}
    explicit operator int() const { return x; }
    modnum& operator+=(const modnum& a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
    modnum& operator-=(const modnum& a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
    modnum& operator*=(const modnum& a) { x = unsigned((static_cast<ull>(x) * a.x) % M); return *this; }
    modnum& operator/=(const modnum& a) { return (*this *= a.inv()); }
    modnum operator+(const modnum& a) const { return (modnum(*this) += a); }
    modnum operator-(const modnum& a) const { return (modnum(*this) -= a); }
    modnum operator*(const modnum& a) const { return (modnum(*this) *= a); }
    modnum operator/(const modnum& a) const { return (modnum(*this) /= a); }
    modnum operator+() const { return *this; }
    modnum operator-() const { modnum a; a.x = x ? (M - x) : 0U; return a; }
    modnum pow(ll e) const {
        if (e < 0) return inv().pow(-e);
        modnum x2 = x, xe = 1U;
        for (; e; e >>= 1) {
            if (e & 1) xe *= x2;
            x2 *= x2;
        }
        return xe;
    }
    modnum inv() const {
        unsigned a = x, b = M; int y = 1, z = 0;
        while (a) {
            const unsigned q = (b/a), c = (b - q*a);
            b = a, a = c; const int w = z - static_cast<int>(q) * y;
            z = y, y = w;
        } assert(b == 1U); return modnum(z);
    }
    friend modnum inv(const modnum& a) { return a.inv(); }
    template<typename T> friend modnum operator+(T a, const modnum& b) { return (modnum(a) += b); }
    template<typename T> friend modnum operator-(T a, const modnum& b) { return (modnum(a) -= b); }
    template<typename T> friend modnum operator*(T a, const modnum& b) { return (modnum(a) *= b); }
    template<typename T> friend modnum operator/(T a, const modnum& b) { return (modnum(a) /= b); }
    explicit operator bool() const { return x; }
    friend bool operator==(const modnum& a, const modnum& b) { return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b) { return a.x != b.x; }
    friend ostream &operator<<(ostream& os, const modnum& a) { return os << a.x; }
    friend istream &operator>>(istream& in, modnum& n) { ull v_; in >> v_; n = modnum(v_); return in; }
};

using mint = modnum<mod>;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, L;
	cin>>n>>L;
	if(n == 1){
		cout<<"1\n";
		return 0;
	}
	vector<int>a(n+1);
	for(int i=0;i<n;i++) cin>>a[i];
	a[n] = 10000;
	sort(a.begin(), a.end());
	vector<vector<array<mint, 3>>>dp(n+2, vector<array<mint, 3>>(L+1)), ndp = dp;
	dp[0][0][0] = 1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;k<=L;k++){
				for(int l=0;l<=2;l++) ndp[j][k][l] = 0;
			}
		}
		for(int j=1;j<=i;j++){
			for(int k=0;k<=L;k++){
				for(int l=0;l<=2;l++){
					int d = (2 * j - l) * (a[i] - a[i-1]);
					if(k < d || i + j + 1 - l > n) continue;
					ndp[j][k][l] += dp[j-1][k-d][l];

					if(l) ndp[j][k][l] += (3 - l) * dp[j-1][k-d][l-1];

					ndp[j][k][l] += (2 * j - l) * dp[j][k-d][l];

					if(l == 1) ndp[j][k][l] += 2 * j * dp[j][k-d][l-1];
					else if(l == 2){
						if(i == n) ndp[j][k][l] += dp[j][k-d][l-1];
						else if(j > 1) ndp[j][k][l] += (j - 1) * dp[j][k-d][l-1];
					}

					if(l == 2){
						if(i == n) ndp[j][k][l] += dp[j+1][k-d][l];
						else ndp[j][k][l] += j * (j - 1) * dp[j+1][k-d][l];
					}
					else if(l == 1) ndp[j][k][l] += j * j * dp[j+1][k-d][l];
					else ndp[j][k][l] += j * (j + 1) * dp[j+1][k-d][l];
				}
			}
		}
		swap(dp, ndp);
	}
	mint ans = 0;
	for(int k=0;k<=L;k++) ans += dp[1][k][2];
	cout<<ans<<"\n";

	return 0;
}
/*
[  ]Leu o problema certo???
[  ]Ver se precisa de long long
[  ]Viu o limite dos fors (é n? é m?)
[  ]Tamanho do vetor, será que é 2e5 em vez de 1e5??
[  ]Testar sample
[  ]Testar casos de  borda
[  ]1LL no 1LL << i
[  ]Testar mod (é 1e9+7, mesmo?, será que o mod não ficou negativo?)
*/

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