Submission #362506

#	Time	Username	Problem	Language	Result	Execution time	Memory
362506		denkendoemeer	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	234 ms	260652 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define mod 1000000007
using namespace std;
int v[105],n,l;
ll dp[105][105][1005][3];
ll calc(int i,int j,int k,int nr)
{
    if (i && (j<=0 || nr>2))
        return 0;
    ll &ans=dp[i][j][k][nr];
    if (ans!=-1)
        return ans;
    if (i==n)
        return (j==1 && nr==2);
    int aux=(v[i+1]-v[i])*(2*j-nr)+k;
    if (aux>l)
        return 0;
    ans=(2*j-nr)*calc(i+1,j,aux,nr)%mod;
    ans=(ans+(2-nr)*calc(i+1,j+1,aux,nr+1))%mod;
    ans=(ans+(2-nr)*calc(i+1,j,aux,nr+1))%mod;
    ans=(ans+(j+1-nr)*calc(i+1,j+1,aux,nr))%mod;
    ans=(ans+(j-1)*calc(i+1,j-1,aux,nr))%mod;
    return ans;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i;
    scanf("%d%d",&n,&l);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    sort(v+1,v+n+1);
    v[0]=v[1];
    memset(dp,-1,sizeof(dp));
    if (n==1){
        printf("1\n");
    }
    else
        printf("%lld\n",calc(0,0,0,0));
return 0;
}

Compilation message (stderr)

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

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