Submission #1160878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160878		Der_Vlapos	Skyscraper (JOI16_skyscraper)	C++20	20 / 100	2096 ms	10896 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()

const int N = 103, L = 1003;
int dp[N][L][4];
int ndp[N][L][4];
const int mod = 1e9 + 7;

struct test
{
    inline int add(int x, int y)
    {
        return (x + y) % mod;
    }
    inline int mul(int x, int y)
    {
        return (1LL * x * y) % mod;
    }

    void solve()
    {
        int n, l;
        cin >> n >> l;
        if (n == 1)
        {
            cout << "1\n";
            return;
        }
        vector<int> a(n);
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(all(a));

        dp[1][0][0] = 1;
        dp[1][0][1] = 2;

        for (int id = 1; id < n; ++id)
        {
            {
                int delta = a[id] - a[id - 1];
                for (int i = 1; i <= n; ++i)
                    for (int j = l; j >= 0; --j)
                        for (int f = 0; f < 3; ++f)
                        {
                            dp[i][j][f] = (j >= delta * (i * 2 - f) ? dp[i][j - (delta * (i * 2 - f))][f] : 0);
                        }
            }

            for (int i = 1; i <= n; ++i)
                for (int j = 0; j <= l; ++j)
                    for (int f = 0; f < 3; ++f)
                        if (dp[i][j][f])
                        {
                            ndp[i][j][f] = add(ndp[i][j][f], mul(dp[i][j][f], (i * 2 - f)));
                            ndp[i + 1][j][f] = add(ndp[i + 1][j][f], mul(dp[i][j][f], (i + 1 - f)));
                            ndp[i - 1][j][f] = add(ndp[i - 1][j][f], mul(dp[i][j][f], (i - 1)));

                            ndp[i][j][f + 1] = add(ndp[i][j][f + 1], mul(dp[i][j][f], (2 - f)));
                            ndp[i + 1][j][f + 1] = add(ndp[i + 1][j][f + 1], mul(dp[i][j][f], (2 - f)));
                        }

            cerr << id << ":\n";
            for (int i = 1; i <= n; ++i)
                for (int j = 0; j <= l; ++j)
                    for (int f = 0; f < 3; ++f)
                    {
                        dp[i][j][f] = ndp[i][j][f];
                        ndp[i][j][f] = 0;
                        if (dp[i][j][f])
                            cerr << i << " " << j << " " << f << ": " << dp[i][j][f] << "\n";
                    }
        }

        int sum = 0;
        for (int i = 0; i <= l; ++i)
            sum = add(sum, dp[1][i][2]);
        cout << sum << "\n";
    }
};

main()
{
    test t;
    t.solve();
}

Compilation message (stderr)

skyscraper.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main()
      | ^~~~

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