Submission #1150022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150022		cpismylifeOwO	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	382 ms	316724 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 1e2 + 5;
const int MaxK = 1e3 + 5;


int n, l;
int arr[MaxN];

void Inp()
{
    cin >> n >> l;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
    sort(arr + 1, arr + n + 1, greater<int>());
}

long long F[2][2][MaxN][MaxN][MaxK];

void Exc()
{
    if (n == 1)
    {
         cout << 1;
         return;
    }
    F[0][0][0][0][0] = 1;
    for (int x = 1; x <= n; x++)
    {
        for (int le = 0; le < 2; le++)
        {
            for (int ri = 0; ri < 2; ri++)
            {
                for (int y = 1; y <= n; y++)
                {
                    for (int z = 0; z <= l; z++)
                    {
                        long long& res = F[le][ri][x][y][z];
                        res = 0;
                        if (x < n && ((le == 1) + (ri == 1) > y))
                        {
                            continue;
                        }
                        int p = z - (2 * y - (le == 1) - (ri == 1)) * (arr[x] - arr[x + 1]);
                        if (p < 0)
                        {
                            continue;
                        }
                        res = (res + F[le][ri][x - 1][y][p] * (2 * y - (le == 1) - (ri == 1)) % mod) % mod;
                        if (le == 1 && y > 0)
                        {
                            res = (res + F[0][ri][x - 1][y - 1][p]) % mod;
                        }
                        if (ri == 1 && y > 0)
                        {
                            res = (res + F[le][0][x - 1][y - 1][p]) % mod;
                        }
                        if (y > 0)
                        {
                            res = (res + F[le][ri][x - 1][y - 1][p]) % mod;
                        }
                        if (y < n)
                        {
                            int k = y + 1 - (le == 1) - (ri == 1);
                            long long m = ((le == 1) * k + (ri == 1) * k + 1ll * (k - 1) * k + (y == 1 && le == 1 && ri == 1 && x == n)) % mod;
                            res = (res + F[le][ri][x - 1][y + 1][p] * m % mod) % mod;
                            //if (le == 0 && ri == 1 && x == 3 && y == 1 && z == 5 && res > 0) cout << k << " ";
                        }
                        if (le == 1)
                        {
                            int k = y - (ri == 1 && x < n);
                            res = (res + F[0][ri][x - 1][y][p] * k % mod) % mod;
                        }
                        if (ri == 1)
                        {
                            int k = y - (le == 1 && x < n);
                            res = (res + F[le][0][x - 1][y][p] * k % mod) % mod;
                        }
                    }
                }
            }
        }
    }
    //cout << F[0][1][3][1][5] << " ";
    long long res = 0;
    for (int x = 0; x <= l; x++)
    {
        res = (res + F[1][1][n][1][x]) % mod;
        //cout << F[1][1][n][1][x] << " ";
    }
    cout << res;
}

int main()
{
    //freopen("C.INP", "r", stdin);
    //freopen("C.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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