제출 #987730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987730		underwaterkillerwhale	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	199 ms	126020 KiB

skyscraper

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 100 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const ll INF = 1e9;
const int BASE = 137;

int n, L;
int a[N];
int dp[N][N * 10][N][3];

inline void add (int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

void solution () {
    cin >> n >> L;
    rep (i, 1, n) cin >> a[i];
    sort (a + 1, a + 1 + n);
    if (n == 1) dp[1][0][0][2] = 1;
    dp[1][0][2][0] = 1;
    dp[1][0][1][1] = 2;

    rep (i, 1, n - 1) {
        int D = a[i + 1] - a[i];
        rep (j, 0, L)
        rep (k, 0, n) {
            int newcost = j + 2 * D * (k - 1);
            if (newcost <= L && k >= 3) {
                add (dp[i + 1][newcost][k][0], 1LL * dp[i][j][k][0] * 2 % Mod * (k - 2) % Mod);
                add (dp[i + 1][newcost][k + 1][0], 1LL * dp[i][j][k][0] * (k - 2) % Mod);
                add (dp[i + 1][newcost][k - 1][0], 1LL * dp[i][j][k][0] * (k - 2) % Mod);
//                if (i + 1 == 3 && newcost == 4) {
//                    cout << i<<","<<j<<","<<k<<","<<0<<": "<<dp[i][j][k][0] <<"\n";
//                }
            }
            if (newcost <= L && k >= 2) {
                add (dp[i + 1][newcost][k - 1][1], 1LL * dp[i][j][k][0] * 2 % Mod);
                add (dp[i + 1][newcost][k][1], 1LL * dp[i][j][k][0] * 2 % Mod);
                add (dp[i + 1][newcost][k][0], 1LL * dp[i][j][k][0] * 2 % Mod);
                add (dp[i + 1][newcost][k + 1][0], 1LL * dp[i][j][k][0] * 2 % Mod);
//                if (i + 1 == 3 && newcost == 4) {
//                    cout << i<<","<<j<<","<<k<<","<<0<<": "<<dp[i][j][k][0] <<" ji\n";
//                }
            }
            newcost = j + 2 * D * (k - 1) + D;
            if (newcost <= L && k >= 2) {
                add (dp[i + 1][newcost][k][1], 1LL * dp[i][j][k][1] * 2 % Mod * (k - 1) % Mod);
                add (dp[i + 1][newcost][k + 1][1], 1LL * dp[i][j][k][1] * (k - 1) % Mod);
                add (dp[i + 1][newcost][k - 1][1], 1LL * dp[i][j][k][1] * (k - 1) % Mod);

            }
            if (newcost <= L && k >= 1) {
                add (dp[i + 1][newcost][k][2], dp[i][j][k][1]);
                add (dp[i + 1][newcost][k - 1][2], dp[i][j][k][1]);
                add (dp[i + 1][newcost][k][1], dp[i][j][k][1]);
                add (dp[i + 1][newcost][k + 1][1], dp[i][j][k][1]);
            }
            newcost = j + 2 * D * k;
            if (newcost <= L && k >= 1) {
                add (dp[i + 1][newcost][k][2], 1LL * dp[i][j][k][2] * 2 % Mod * k % Mod);
                add (dp[i + 1][newcost][k + 1][2], 1LL * dp[i][j][k][2] * k % Mod);
                add (dp[i + 1][newcost][k - 1][2], 1LL * dp[i][j][k][2] * k % Mod);
//                if (i + 1 == 3 && newcost == 3) {
//                    cout << i<<","<<j<<","<<k<<","<<2<<": "<<dp[i][j][k][2] <<" ji\n";
//                }
            }
        }
    }
    ll res = 0;
    rep (i, 0, L) {
        (res += dp[n][i][0][2]) %= Mod;
    }
    cout << res <<"\n";
}

#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);

int main () {
//    file("teamwork");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1, dummy;
//    cin >> dummy >> num_Test;
    while(num_Test--)
        solution();
}
/*
*/

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:98:22: warning: unused variable 'dummy' [-Wunused-variable]
   98 |     ll num_Test = 1, dummy;
      |                      ^~~~~

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