Submission #225536

#	Time	Username	Problem	Language	Result	Execution time	Memory
225536		MKopchev	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	123 ms	130552 KiB

skyscraper

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

const int nmax=1e2+5,lmax=1e3+5,mod=1e9+7;

int n,inp[nmax];

int dp[nmax][nmax][lmax][3];

int mx;

int rec(int placed,int components,int sum,int ends)
{
    if(ends>2||sum>mx)return 0;

    if(components==0&&placed)return 0;

    if(placed==n)return ends==2&&components==1;

    if(dp[placed][components][sum][ends]!=-1)return dp[placed][components][sum][ends];

    int sum_new=sum+(inp[placed+1]-inp[placed])*(2*components-ends);

    long long ret=0;

    if(components>=2)ret=ret+1LL*(components-1)*rec(placed+1,components-1,sum_new,ends);//merge 2 components

    if(components>=1)ret=ret+1LL*(2*components-ends)*rec(placed+1,components,sum_new,ends);//add to a component's end

    ret=ret+1LL*(components+1-ends)*rec(placed+1,components+1,sum_new,ends);//create a new component

    if(ends<2)ret=ret+1LL*(2-ends)*rec(placed+1,components+1,sum_new,ends+1);//create a new end

    if(ends<2)ret=ret+1LL*(2-ends)*rec(placed+1,components,sum_new,ends+1);//extend a component to make it a border

    ret=ret%mod;

    dp[placed][components][sum][ends]=ret;

    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));

    scanf("%i%i",&n,&mx);
    for(int i=1;i<=n;i++)scanf("%i",&inp[i]);

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

    sort(inp+1,inp+n+1);

    printf("%i\n",rec(0,0,0,0));
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&mx);
     ~~~~~^~~~~~~~~~~~~~~
skyscraper.cpp:47:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

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