Submission #559047

#	Time	Username	Problem	Language	Result	Execution time	Memory
559047		groshi	Tents (JOI18_tents)	C++17	100 / 100	233 ms	83020 KiB

tents

#include<iostream>

using namespace std;
int mod=1000000007;
long long dp[4000][4000];
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int h,w;
    cin>>h>>w;
    dp[1][1]=1;
    for(int i=2;i<=h+1;i++)
    {
        for(int j=2;j<=w+1;j++)
        {
            if(i==2)
                dp[i][j]=1;
            else dp[i][j]=dp[i-1][j];
            if(i==2 || j==2)
                dp[i][j]+=(j-1)*4;
            else dp[i][j]+=(j-1)*4*dp[i-1][j-1];
            dp[i][j]%=mod;
            if(i==3 || j==2)
                dp[i][j]+=(j-1)*(i-2);
            else dp[i][j]+=(j-1)*(i-2)*dp[i-2][j-1];
            dp[i][j]%=mod;
            if(i==2 || j==3)
                dp[i][j]+=(j-1)*(j-2)/2;
            else dp[i][j]+=((j-1)*(j-2)/2)*dp[i-1][j-2];
            dp[i][j]%=mod;
        }
    }
    cout<<dp[h+1][w+1]-1;
    return 0;
}

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