Submission #737094

#	Time	Username	Problem	Language	Result	Execution time	Memory
737094		danikoynov	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	151 ms	122188 KiB

skyscraper

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 110, maxl = 1e3 + 10;
const ll mod = 1e9 + 7;
int n, l, a[maxn];

void add(ll &cell, ll val)
{
    val %= mod;
    cell += val;
    if (cell >= mod)
        cell -= mod;
}

ll dp[maxn][maxl][maxn][3];
void solve()
{
    cin >> n >> l;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];

    sort(a + 1, a + n + 1);
    a[n + 1] = a[n];
    if (n == 1)
    {
        cout << 1 << endl;
        return;
    }

    if (n == 2)
    {
        if (a[2] - a[1] <= l)
        {
            cout << 2 << endl;
        }
        else
        {
            cout << 0 << endl;
        }
        return;
    }

    dp[1][2 * (a[2] - a[1])][1][0] = 1;
    dp[1][a[2] - a[1]][1][1] = 1;
    ///cout << a[1] << " " << a[2] << endl;
    for (int i = 1; i < n; i ++)
    {
        for (int j = 0; j <= l; j ++)
        {
            for (int k = 0; k <= n; k ++)
            {
                for (int p = 0; p < 3; p ++)
                {
                    if (dp[i][j][k][p] == 0)
                        continue;
                    ///cout << i << " " << j << " " << k << " " << p << " " << dp[i][j][k][p] << endl;
                    int new_diff = j + (k * 2 - p + 2) * (a[i + 2] - a[i + 1]); /// add a new component
                    ///cout << new_diff << endl;
                    if (new_diff <= l)
                        add(dp[i + 1][new_diff][k + 1][p], dp[i][j][k][p] * (ll)(k + 1 - p));
                    new_diff = j + (k * 2 - p) * (a[i + 2] - a[i + 1]); /// add to an existing component
                    ///cout << new_diff << endl;
                    if (new_diff <= l)
                        add(dp[i + 1][new_diff][k][p], dp[i][j][k][p] * (ll)((k * 2 - p)));
                    if (p != 2)
                    {
                        new_diff = j + (k * 2 - p - 1) * (a[i + 2] - a[i + 1]);

                        if (new_diff <= l)
                            add(dp[i + 1][new_diff][k][p + 1], dp[i][j][k][p]);

                        new_diff = j + (k * 2 - p + 1) * (a[i + 2] - a[i + 1]);

                        if (new_diff <= l)
                            add(dp[i + 1][new_diff][k + 1][p + 1], dp[i][j][k][p]);
                    }
                    new_diff = j + (k * 2 - p - 2) * (a[i + 2] - a[i + 1]);
                    //cout << i << " " << j << " " << k << " " << p << " " << dp[i][j][k][p] << endl;
                      //  cout << new_diff << endl;
                    if (new_diff <= l && k > 1)
                        add(dp[i + 1][new_diff][k - 1][p], dp[i][j][k][p] * (k - 1));
                }
            }
        }
    }

    ll ans = 0;
    for (int s = 0; s <= l; s ++)
    {
        ans = ans + dp[n][s][1][2];
        ///cout << s << " :: " << dp[n][s][1][2] << endl;
        if (ans >= mod)
        ans -= mod;
    }
    cout << (ans * 2)% mod << endl;

}

int main()
{
    solve();
    return 0;
}

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