Submission #41707

#	Time	Username	Problem	Language	Result	Execution time	Memory
41707		fallingstar	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	89 ms	16376 KiB

skyscraper

/**
    Problem: Skyscraper
    Source: JOI Open Contest 2016 Problem 3
    Solution: Connected Component DP
*/

#include <cstdio>
#include <algorithm>

using namespace std;

#define long long long

const int N = 100 + 2;
const int MOD = 1e9 + 7;
const int L = 1000 + 2;

void AddMod(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
int MulMod(int a, int b) { return (long) a * b % MOD; }

int n, lim, a[N], dp[N][N][L][3];

int main()
{
    scanf("%d %d", &n, &lim);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);

    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= i; ++j)
            for (int k = 0; k <= lim; ++k)
                for (int l = 0; l <= 2; ++l)
                {
                    int new_k = k + (a[i + 1] - a[i]) * (j * 2 - l);
                    if (new_k > lim || !dp[i][j][k][l]) continue;

                    // add new component
                    AddMod(dp[i + 1][j + 1][new_k][l], MulMod(dp[i][j][k][l], j - 1 + 2 - l));
                    if (l < 2) AddMod(dp[i + 1][j + 1][new_k][l + 1], MulMod(dp[i][j][k][l], 2 - l));

                    // connect two component
                    if (j >= 2) AddMod(dp[i + 1][j - 1][new_k][l], MulMod(dp[i][j][k][l], j - 1));

                    // to component's end
                    if (j > 0) AddMod(dp[i + 1][j][new_k][l], MulMod(dp[i][j][k][l], j * 2 - l));
                    if (j > 0 && l < 2) AddMod(dp[i + 1][j][new_k][l + 1], MulMod(dp[i][j][k][l], 2 - l));
                }

    int res = 0;
    for (int k = 0; k <= lim; ++k)
        AddMod(res, dp[n][1][k][2]);

    printf("%d", n > 1 ? res : 1);
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:25:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &lim);
                             ^
skyscraper.cpp:26:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
                                                    ^

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