Submission #220308

#	Time	Username	Problem	Language	Result	Execution time	Memory
220308		MKopchev	Tents (JOI18_tents)	C++14	100 / 100	222 ms	35968 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const int nmax=3e3+5,mod=1e9+7,fourth=(mod+1)/4;
int dp[nmax][nmax];

int h,w;

int rec(int row,int free)
{
    if(row>h)return 1;
    if(dp[row][free]!=-1)return dp[row][free];

    int ret=rec(row+1,free);//do not place

    //place one

    //on new and alone
    if(free)ret=(ret+4LL*(free)*rec(row+1,free-1))%mod;
    //on old(force with some other)
    if(free&&row<h)ret=(ret+1LL*free*(h-row)%mod*rec(row+2,free-1))%mod;

    //place two
    if(free>=2)ret=(ret+1LL*free*(free-1)/2*rec(row+1,free-2))%mod;

    dp[row][free]=ret;
    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));

    scanf("%i%i",&h,&w);

    int output=rec(1,w);

    output=(output+mod-1)%mod;

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

Compilation message (stderr)

tents.cpp: In function 'int main()':
tents.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&h,&w);
     ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52