Submission #558834

#	Time	Username	Problem	Language	Result	Execution time	Memory
558834		hibiki	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	169 ms	81800 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define pb push_back

int n,l;
long long dp[105][105][1005][3];
vector<int> v;

int main()
{
    scanf("%d %d",&n,&l);
    for(int i = 0; i < n; i++)
    {
        int a;
        scanf("%d",&a);
        v.pb(a);
    }

    sort(v.begin(), v.end());

    if(n==1)
    {
        printf("1\n");
        return 0;
    }

    dp[0][1][0][0]=1;
    dp[0][1][0][1]=2;
    for(int idx = 0; idx < n - 1; idx++)
    {
        for(int g = 1; g <= idx + 1; g++)
        {
            for(int val = 0; val <= l; val++)
            {
                for(int ex = 0; ex < 3; ex++)
                {
                    // let's say we have ex = 0
                    // means we have space for start and end ex place(s)
                    long long cur = val + (2 * g - ex) * (v[idx + 1] - v[idx]);
                    long long nw = dp[idx][g][val][ex];
                    if(cur > l) continue;

                    // merge at start or end
                    dp[idx + 1][g][cur][ex + 1] += (2 - ex) * nw;
                    dp[idx + 1][g][cur][ex + 1] %= mod;

                    // create g at start or end;
                    dp[idx + 1][g + 1][cur][ex + 1] += (2 - ex) * nw;
                    dp[idx + 1][g + 1][cur][ex + 1] %= mod;

                    // merge
                    dp[idx + 1][g - 1][cur][ex] += (g - 1) * nw;
                    dp[idx + 1][g - 1][cur][ex] %= mod;

                    // create g
                    dp[idx + 1][g + 1][cur][ex] += (g + 1 - ex) * nw;
                    dp[idx + 1][g + 1][cur][ex] %= mod;

                    // add to g
                    dp[idx + 1][g][cur][ex] += (2 * g - ex) * nw;
                    dp[idx + 1][g][cur][ex] %= mod;
                }
            }
        }
    }

    long long ans = 0;
    for(int i = 0; i <= l; i++)
    {
        ans = ( ans + dp[n-1][1][i][2] ) % mod;
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d",&n,&l);
      |     ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

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