Submission #649355

#	Time	Username	Problem	Language	Result	Execution time	Memory
649355		ToroTN	Skyscraper (JOI16_skyscraper)	C++14	0 / 100	2 ms	852 KiB

skyscraper

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

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,&len);
      |     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

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