제출 #883078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
883078		adaawf	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	121 ms	220048 KiB

skyscraper

#include <iostream>
#include <algorithm>
using namespace std;
long long int a[105], f[105][105][1005][3], mod = 1e9 + 7;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, x;
    cin >> n >> x;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (n == 1) {
        cout << 1;
        return 0;
    }
    sort(a + 1, a + n + 1);
    f[1][1][0][0] = 1;
    f[1][1][0][1] = 2;
    for (long long int i = 1; i < n; i++) {
        for (long long int j = 0; j <= i; j++) {
            for (long long int k = 0; k <= x; k++) {
                for (long long int l = 0; l <= 2; l++) {
                    f[i][j][k][l] %= mod;
                    if (f[i][j][k][l] == 0) continue;
                    long long int h = k + (a[i + 1] - a[i]) * (j * 2 - l);
                    if (h > x) continue;
                    if (j >= 2) f[i + 1][j - 1][h][l] += f[i][j][k][l] * (j - 1) % mod;
                    if (j >= 1) f[i + 1][j][h][l] += f[i][j][k][l] * (j * 2 - l) % mod;
                    if (l < 2) f[i + 1][j + 1][h][l + 1] += f[i][j][k][l] * (2 - l) % mod;
                    if (l < 2 && j >= 1) f[i + 1][j][h][l + 1] += f[i][j][k][l] * (2 - l) % mod;
                    f[i + 1][j + 1][h][l] += f[i][j][k][l] * (j + 1 - l) % mod;
                }
            }
        }
    }
    long long int res = 0;
    for (int i = 0; i <= x; i++) {
        res += f[n][1][i][2] % mod;
        res %= mod;
    }
    cout << res;
}

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