제출 #650038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
650038		Gromp15	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	2083 ms	19548 KiB

skyscraper

#include <bits/stdc++.h>
#define ll long long
#define ar array
using namespace std;
const int mod = 1e9+7;
void fadd(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
}
int mul(int a, int b) {
    return (ll)a*b%mod;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, L; cin >> n >> L;
    vector<int> t(n);
    for (int &x : t) cin >> x;
    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }
    sort(t.begin(), t.end());
    vector<map<int, ar<int, 4>>> dp(n+1);
    // [# of components][total sum rn][(leftmost element filled) + (rightmost element filled)*2]
    dp[0][0][0] = 1;
    for (int i = 0; i < n; i++) {
        vector<map<int, ar<int, 4>>> dp2(n+1);
        for (int j = 0; j <= n; j++) {
            for (const auto &[l, val] : dp[j]) {
                for (int tp = 0; tp < 4; tp++) {
                    int num = val[tp];
                    if (!num) continue;
                    if (j > 1) { // merge
                        fadd(dp2[j-1][l+2*t[i]][tp], mul(num, j-1));
                    }
                    if (j > 0) { // add to comp
                        if (2*j-(tp&1)-(tp >> 1 & 1) > 0) fadd(dp2[j][l][tp], mul(num, 2*j-(tp&1)-(tp >> 1 & 1)));
                        if (!(tp & 1)) fadd(dp2[j][l+t[i]][tp|1], num);
                        if (!(tp >> 1 & 1)) fadd(dp2[j][l+t[i]][tp|2], num);
                    }
                    if (j+1 <= n) { // new comp
                        if (j+1-(tp&1)-(tp >> 1 & 1) > 0) fadd(dp2[j+1][l-2*t[i]][tp], mul(j+1-(tp&1)-(tp >> 1 & 1), num));
                        if (!(tp & 1)) fadd(dp2[j+1][l-t[i]][tp|1], num);
                        if (!(tp >> 1 & 1)) fadd(dp2[j+1][l-t[i]][tp|2], num);
                    }
                }
            }
        }
        swap(dp, dp2);
    }
    int ans = 0;
    for (int i = 0; i <= L; i++) { 
        fadd(ans, dp[1][i][3]);
    }
    cout << ans << '\n';
}

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