Submission #649359

#	Time	Username	Problem	Language	Result	Execution time	Memory
649359		ToroTN	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	347 ms	79644 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[105],dp[105][105][1005][3],len,ans,cost;
void sum(ll a,ll b)
{
    a+=b;
    a%=1000000007;
}
ll md(ll a)
{return (a+1000000007)%1000000007;}
int main()
{
    scanf("%lld%lld",&n,&len);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    if(n==1)
    {
        printf("1\n");
        return 0;
    }
    sort(a+1,a+n+1);
    /*for(int i=1;i<=n;i++)
    {
        printf("%d ",a[i]);
    }
    printf("\n");*/
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<=len;k++)
            {
                for(int l=0;l<=2;l++)
                {
                    cost=md(md((2*(a[i+1]-a[i])*j)-(a[i+1]-a[i])*l));
                    if(k+cost>len)continue;
                    for(int c=-1;c<=1;c++)
                    {
                        if(j+c>=1)
                        {
                            if(c==0)
                            {
                                dp[i+1][j+c][k+cost][l]+=md(md(dp[i][j][k][l]*(j-1))*2);
                            }else
                            {
                                dp[i+1][j+c][k+cost][l]+=md(dp[i][j][k][l]*(j-1));
                            }
                            dp[i+1][j+c][k+cost][l]%=1000000007;
                            if(c>=0)
                            {
                                dp[i+1][j+c][k+cost][l]+=md(dp[i][j][k][l]*(2-l));
                                dp[i+1][j+c][k+cost][l]%=1000000007;
                            }
                        }
                    }
                    if(l<=1)
                    {
                        for(int c=0;c<=1;c++)
                        {
                            dp[i+1][j+c][k+cost][l+1]+=md(dp[i][j][k][l]*(2-l));
                            dp[i+1][j+c][k+cost][l+1]%=1000000007;
                        }
                    }
                }
            }
        }
    }
    //printf("%d\n",dp[2][2][2][0]);
    for(int i=0;i<=len;i++)
    {
        ans+=dp[n][1][i][2];
        ans%=1000000007;
    }
    printf("%lld\n",ans);
}

Compilation message (stderr)

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

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