Submission #1220225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220225		QuocSensei	Skyscraper (JOI16_skyscraper)	C++20	15 / 100	1 ms	1352 KiB

skyscraper

#include<bits/stdc++.h>

#define ll long long
#define el cout << '\n'

using namespace std;

const int maxn = 1e2;
const int maxl = 1e3;
const int MOD = 1e9 + 7;

int n, l, a[maxn + 10];
ll dp[maxn + 10][maxn + 10][maxl + 10][5], ans = 0;

void add(ll &a, ll b)
{
    b %= MOD;
    a += b;
    if (a >= MOD) a -= MOD;
}
int cost(int i, int j, int k, int z)
{
    return min(l + 1, k + (2 * j - z) * (a[i + 2] - a[i + 1]));
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("SKYSCRAPER.INP", "r"))
    {
        freopen("SKYSCRAPER.INP", "r", stdin);
        freopen("SKYSCRAPER.OUT", "w", stdout);
    }

    cin >> n >> l;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    a[n + 1] = 1e5;
    dp[0][0][0][0] = 1;
    for (int i = 0; i < n; i++)
    {
        int nxt_i = i + 1;
        int curr_i = i;
        for (int j = 0; j <= i + 1; j++)
            for (int k = 0; k <= l; k++)
                for (int z = 0; z <= 2; z++)
                {
                    dp[nxt_i][j][k][z] = 0;
                }
        for (int j = 0; j <= i + 1; j++)
            for (int k = 0; k <= l; k++)
                for (int z = 0; z <= min(j, 2); z++)
                {
                    ll val = dp[curr_i][j][k][z];

                    add(dp[nxt_i][j][cost(i, j, k, z)][z], (2 * j - z) * val);
                    if (i < n - 1 || z < 1 || j != 1)
                        add(dp[nxt_i][j][cost(i, j, k, z + 1)][z + 1], (2 - z) * (j - z) * val);
                    else
                        add(dp[nxt_i][j][cost(i, j, k, z + 1)][z + 1], val);
                    add(dp[nxt_i][j + 1][cost(i, j + 1, k, z)][z], val);
                    if (z <= 1)
                        add(dp[nxt_i][j + 1][cost(i, j + 1, k, z + 1)][z + 1], (2 - z) * val);
                    if ((i < n - 1 || z < 2 || j != 2) && j)
                        add(dp[nxt_i][j - 1][cost(i, j - 1, k, z)][z], ((j - z) * (j - 1)) * val);
                    else if (j)
                        add(dp[nxt_i][j - 1][cost(i, j - 1, k, z)][z], val);
                }
    }
//    cout << cost(1, 2, 2, 1), el;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//            for (int k = 0; k <= l; k++)
//                for (int z = 0; z <= 2; z++)
//                {
//                    ll val = dp[i][j][k][z];
//                    if (val)
//                        cout << i << ' ' << j << ' ' << k << ' ' << z << ' ' << val << '\n';
//                }
    for (int i = 0; i <= l; i++)
        add(ans, dp[n][1][i][2]);
    cout << ans;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen("SKYSCRAPER.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:32:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |         freopen("SKYSCRAPER.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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