oj.uz

Submission #445513

# Submission time Handle Problem Language Result Execution time Memory
445513 2021-07-18T12:22:58 Z KYoA_A Skyscraper (JOI16_skyscraper) C++17
100 / 100
 252 ms 120772 KB 
/*---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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 120656 KB Output is correct
2 Correct 62 ms 120568 KB Output is correct
3 Correct 64 ms 120616 KB Output is correct
4 Correct 64 ms 120580 KB Output is correct
5 Correct 63 ms 120648 KB Output is correct
6 Correct 63 ms 120636 KB Output is correct
7 Correct 65 ms 120600 KB Output is correct
8 Correct 64 ms 120580 KB Output is correct
9 Correct 65 ms 120584 KB Output is correct
10 Correct 64 ms 120664 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 120560 KB Output is correct
2 Correct 68 ms 120644 KB Output is correct
3 Correct 70 ms 120560 KB Output is correct
4 Correct 66 ms 120644 KB Output is correct
5 Correct 66 ms 120568 KB Output is correct
6 Correct 67 ms 120604 KB Output is correct
7 Correct 66 ms 120648 KB Output is correct
8 Correct 68 ms 120612 KB Output is correct
9 Correct 66 ms 120620 KB Output is correct
10 Correct 67 ms 120628 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 120656 KB Output is correct
2 Correct 62 ms 120568 KB Output is correct
3 Correct 64 ms 120616 KB Output is correct
4 Correct 64 ms 120580 KB Output is correct
5 Correct 63 ms 120648 KB Output is correct
6 Correct 63 ms 120636 KB Output is correct
7 Correct 65 ms 120600 KB Output is correct
8 Correct 64 ms 120580 KB Output is correct
9 Correct 65 ms 120584 KB Output is correct
10 Correct 64 ms 120664 KB Output is correct
11 Correct 66 ms 120560 KB Output is correct
12 Correct 68 ms 120644 KB Output is correct
13 Correct 70 ms 120560 KB Output is correct
14 Correct 66 ms 120644 KB Output is correct
15 Correct 66 ms 120568 KB Output is correct
16 Correct 67 ms 120604 KB Output is correct
17 Correct 66 ms 120648 KB Output is correct
18 Correct 68 ms 120612 KB Output is correct
19 Correct 66 ms 120620 KB Output is correct
20 Correct 67 ms 120628 KB Output is correct
21 Correct 95 ms 120656 KB Output is correct
22 Correct 176 ms 120592 KB Output is correct
23 Correct 177 ms 120696 KB Output is correct
24 Correct 209 ms 120636 KB Output is correct
25 Correct 177 ms 120644 KB Output is correct
26 Correct 192 ms 120680 KB Output is correct
27 Correct 246 ms 120676 KB Output is correct
28 Correct 252 ms 120732 KB Output is correct
29 Correct 243 ms 120772 KB Output is correct
30 Correct 176 ms 120664 KB Output is correct