제출 #1276998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276998		tin_le	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	166 ms	240220 KiB

skyscraper

#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
#include<numeric>
using namespace std;
using ll = long long;
#define int ll
using ld = long double;
using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);
using pll = pair<ll, ll>;
using pi = pair<int, int>;
#define f first
#define s second
#define mp make_pair
#define deb false
#define INF 1e18
#define mod1 1000000007
#define mod2 998244353
#define N 100001
#define logN 22
#define endl "\n"
#define hash1 10007
#define hash2 1009
#define rep(i, a, b) for (int i = a; i <= b; ++i)
typedef tree<pi, null_type, less<pi>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int tc = 1, t = 1;

long long binpow(long long a, long long b, long long m) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m;
        b >>= 1;
    }
    return res % m;
}

void modplus(int &a, int b) { b %= mod1; a = (a + b) % mod1; }

int dp[101][101][1001][3];
int n, l;
vi wow;

int rec(int i, int j, int k, int s) {
    if (k > l) return 0;
    if (i == n - 1) return (j == 1 && s == 2) ? 1 : 0;
    if (j < 1 || j > n) return 0;
    int &memo = dp[i][j][k][s];
    if (memo != -1) return memo;
    int d = wow[i + 1] - wow[i];
    int res = 0;
    if (s == 0) {
        int cost = 2 * j * d;
        if (k + cost <= l) {
            res = (res + ( (j - 1) * rec(i + 1, j - 1, k + cost, 0) ) ) % mod1;
            res = (res + ( (j + 1) * rec(i + 1, j + 1, k + cost, 0) ) ) % mod1;
            res = (res + ( (2 * j) * rec(i + 1, j, k + cost, 0) ) ) % mod1;
            res = (res + ( 2 * rec(i + 1, j, k + cost, 1) ) ) % mod1;
            res = (res + ( 2 * rec(i + 1, j + 1, k + cost, 1) ) ) % mod1;
        }
    } else if (s == 1) {
        int cost = (2 * j - 1) * d;
        if (k + cost <= l) {
            res = (res + ( (j - 1) * rec(i + 1, j - 1, k + cost, 1) ) ) % mod1;
            res = (res + ( j * rec(i + 1, j + 1, k + cost, 1) ) ) % mod1;
            res = (res + ( (2 * j - 1) * rec(i + 1, j, k + cost, 1) ) ) % mod1;
            res = (res + rec(i + 1, j, k + cost, 2)) % mod1;
            res = (res + rec(i + 1, j + 1, k + cost, 2)) % mod1;
        }
    } else {
        int cost = (2 * j - 2) * d;
        if (k + cost <= l) {
            res = (res + ( (j - 1) * rec(i + 1, j - 1, k + cost, 2) ) ) % mod1;
            res = (res + ( (j - 1) * rec(i + 1, j + 1, k + cost, 2) ) ) % mod1;
            res = (res + ( (2 * j - 2) * rec(i + 1, j, k + cost, 2) ) ) % mod1;
        }
    }
    return memo = (res % mod1 + mod1) % mod1;
}

void solve() {
    cin >> n >> l;
    wow.assign(n, 0);
    for (int i = 0; i < n; i++) cin >> wow[i];
    sort(all(wow));
    if (n == 1) { cout << 1 << endl; return; }
    else if (n == 2) { cout << 2 * ((wow[1] - wow[0]) <= l) % mod1 << endl; return; }
    memset(dp, -1, sizeof(dp));
    int ans = (rec(0, 1, 0, 0) + (2 * rec(0, 1, 0, 1)) % mod1) % mod1;
    cout << ans << endl;
}

int32_t main() {
    fast;
    for (tc = 1; tc <= t; tc++) {
        solve();
    }
    return 0;
}

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