Submission #483425

#	Time	Username	Problem	Language	Result	Execution time	Memory
483425		prvocislo	Skyscraper (JOI16_skyscraper)	C++17	20 / 100	56 ms	15032 KiB

skyscraper

/*░░░░░░░░░░░░░░░░░░░░░░░░░░░░▓▓░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░██████░░░░░░░░░░░░░░░░░░░░░░░░
░░██░░░░░░░░░░░░░░░░░░░░████████░░░░░░░░░░░░░░░░░░░░░░░░
░░██████░░░░░░░░░░░░░░████░░░░██░░░░░░░░░░░░░░░░░░░░░░░░
░░██████████░░░░░░░░████░░░░  ██░░░░░░░░░░░░░░░░░░░░░░░░
░░██░░░░██████████████░░░░    ██░░░░░░░░░░░░░░░░░░░░░░░░
░░██░░  ░░░░░░░░░░░░░░░░░░    ██░░░░░░░░░░░░░░░░░░░░░░░░
░░██░░    ░░░░░░░░░░░░░░░░░░░░████░░░░░░░░░░░░░░░░░░░░░░
░░██░░    ░░░░░░░░░░░░░░░░░░░░░░████░░░░░░░░░░░░░░░░░░░░
░░░░██  ░░░░░░░░░░░░░░░░░░░░░░░░░░████░░░░░░░░░░░░░░░░░░
░░░░██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██░░░░░░░░░░░░░░░░░░
░░░░██░░░░░░░░░░░░░░░░░░░░  ████░░░░████▓▓▓▓▓▓██░░░░░░░░
░░██░░░░░░  ████░░░░░░░░░░████████░░██░░░░░░░░░░██░░░░░░
░░██░░░░░░████████░░░░░░░░████  ██░░██░░░░░░░░░░░░██░░░░
░░██░░░░░░████  ██░░░░░░░░░░████░░██░░░░░░░░░░░░░░░░██░░
░░████  ░░▒▒████▒▒░░░░░░░░░░▒▒▒▒  ██░░████████▓▓░░░░██░░
████████        ░░░░░░░░░░░░░░  ██░░████░░░░░░░░████████
██      ████        ░░░░░░░░  ██████░░░░░░░░░░░░░░░░████
██          ██████    ██████████░░░░░░░░░░░░░░░░░░░░░░██
██                ██████████░░░░░░░░░░░░░░░░░░░░░░░░░░██
██              ░░░░░░░░▒▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░██
██            ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██
██              ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██░░
▒▒▓▓    ░░░░░░  ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██░░
░░██      ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██░░░░
░░░░██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██░░░░░░
░░░░░░████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████░░░░░░░░
░░░░░░░░░░████████████████▓▓▓▓▓▓████████████░░░░░░░░░░*/
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
typedef long long ll;
using namespace std;

const int mod = 1e9 + 7, maxn = 105, maxl = 1005;
void upd(int& a, int b) { a = (a + b) % mod; }
int mul(int a, int b) { return (a * 1ll * b) % ((ll)mod); }
int dp[maxn][maxn][maxl][3], a[maxn];
// dp[pocet cisel][pocet komponentov][momentalny sucet (a_i namiesto otaznikov][pocet koncov]
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, l;
    cin >> n >> l;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (n == 1)
    {
        cout << "1\n";
        return 0;
    }
    sort(a, a + n);
    a[n] = 10000;
    if (a[1] - a[0] <= l) dp[1][1][a[1] - a[0]][1] = 2;
    if ((a[1] - a[0]) * 2 <= l) dp[1][1][(a[1] - a[0]) * 2][0] = 1;
    for (int i = 1; i < n; i++)
    {
        int x = a[i + 1] - a[i];
        for (int cmp = 1; cmp <= i; cmp++)
        {
            for (int sum = 0; sum <= l; sum++)
            {
                for (int e = 0; e < 3; e++)
                {
                    if (!dp[i][cmp][sum][e]) continue;
                    // idem ho umiestnit na kraj
                    if (e < 3)
                    {
                        int merge_sum = sum + x * (2 * (cmp - 1) + 2 - (e + 1));
                        if (merge_sum <= l)
                        {
                            if (i == n - 1) upd(dp[i + 1][cmp][merge_sum][e + 1], dp[i][cmp][sum][e]);
                            else upd(dp[i + 1][cmp][merge_sum][e + 1], mul(dp[i][cmp][sum][e], (2 - e) * (cmp - e)));
                        }
                        int alone_sum = sum + x * (2 * cmp + 2 - (e + 1));
                        if (alone_sum <= l) upd(dp[i + 1][cmp + 1][alone_sum][e + 1], mul(dp[i][cmp][sum][e], 2 - e));
                    }
                    // idem ho dat ako novy komponent
                    int alone_sum = sum + x * (2 * cmp + 2 - e);
                    if (alone_sum <= l) upd(dp[i + 1][cmp + 1][alone_sum][e], dp[i][cmp][sum][e]);
                    // idem ho pripojit na kraj existujuceho komponentu
                    int append_sum = sum + x * (2 * (cmp - 1) + 2 - e);
                    if (append_sum <= l) upd(dp[i + 1][cmp][append_sum][e], dp[i][cmp][sum][e] * (2 * cmp - e));
                    // idem spojit dva komponenty
                    int merge_sum = sum + x * (2 * (cmp - 2) + 2 - e);
                    if (merge_sum <= l && cmp >= 2)
                    {
                        if (e == 0)
                            upd(dp[i + 1][cmp - 1][merge_sum][e], mul(dp[i][cmp][sum][e], cmp * (cmp - 1)));
                        if (e == 1)
                            upd(dp[i + 1][cmp - 1][merge_sum][e], mul(dp[i][cmp][sum][e], (cmp - 1) * (cmp - 1)));
                        if (e == 2 && i == n - 1)
                            upd(dp[i + 1][cmp - 1][merge_sum][e], dp[i][cmp][sum][e]);
                        if (e == 2 && i != n - 1)
                            upd(dp[i + 1][cmp - 1][merge_sum][e], mul(dp[i][cmp][sum][e], (cmp - 1) * (cmp - 2)));
                    }
                }
            }
        }
    }
    int ans = 0;
    for (int sum = 0; sum <= l; sum++) upd(ans, dp[n][1][sum][2]);
    cout << ans << "\n";
    return 0;
}

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