Submission #901447

#	Time	Username	Problem	Language	Result	Execution time	Memory
901447		warner1129	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	56 ms	5212 KiB

skyscraper

#include <bits/stdc++.h>
 
using namespace std;

 
#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
 
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
 
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
 
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

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

    vector<int> A(n);
    for (auto &x : A) cin >> x;

    sort(all(A));

    if (n == 1) {
        cout << 1 << '\n';
        return;
    }

    vector dp(n + 1, vector(3, vector<i64>(L + 1)));
    dp[1][0][0] = 1;
    dp[1][1][0] = 2;
    dp[1][2][0] = 1;

    for (int i = 1; i < n; i++) {
        vector f(n + 1, vector(3, vector<i64>(L + 1)));
        
        for (int j = 1; j <= i; j++)
            for (int k = 0; k <= 2; k++) {
                i64 w = (A[i] - A[i - 1]) * (j * 2 - k);
                
                for (int s = 0; s + w <= L; s++) if (dp[j][k][s]) {
                    i64 way = dp[j][k][s];
                    
                    f[j + 1][k][s + w] += way * (j + 1 - k);
                    f[j][k][s + w] += way * (j * 2 - k);
                    f[j - 1][k][s + w] += way * (j - 1);
                    
                    if (k == 0) {
                        f[j + 1][k + 1][s + w] += way * 2;
                        f[j][k + 1][s + w] += way * 2;
                    }
                    if (k == 1) {
                        f[j + 1][k + 1][s + w] += way;
                        f[j][k + 1][s + w] += way;
                    }
                }
            }
        dp.swap(f);

        for (auto &a : dp)
            for (auto &b : a)
                for (auto &x : b)
                    x %= mod;
    }

    i64 ans = 0;
    for (int i = 0; i <= L; i++)
        (ans += dp[1][2][i]) %= mod;

    cout << ans << '\n';
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

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