Submission #220305

#	Time	Username	Problem	Language	Result	Execution time	Memory
220305		MKopchev	Tents (JOI18_tents)	C++14	48 / 100	255 ms	111480 KiB

tents

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

int h,w;

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

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

    //place one

    //on new
    if(free)ret=(ret+4LL*(free)*rec(row+1,free-1,one_not_forced+1))%mod;
    //on old
    if(one_not_forced)ret=(ret+1LL*fourth*one_not_forced%mod*rec(row+1,free,one_not_forced-1))%mod;

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

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

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

    int output=rec(1,w,0);

    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: 0 / 52