Submission #540577

#	Time	Username	Problem	Language	Result	Execution time	Memory
540577		krit3379	Tents (JOI18_tents)	C++17	100 / 100	278 ms	70828 KiB

tents

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

long long dp[N][N],mod=1e9+7;

int main(){
    int n,m,i,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<=n;i++)for(j=0;j<=m;j++){//dp[i][j]: consider placing up until ith row jth col
        if(!i||!j)dp[i][j]=1;
        else{
            dp[i][j]+=dp[i-1][j];//not place in ith row
            dp[i][j]+=(j*4*dp[i-1][j-1])%mod;//place 1 in ith row while moving other col
            if(j>=2)dp[i][j]+=((j*(j-1)/2)*dp[i-1][j-2])%mod;// place <> choose (i,j1),(i,j2) and move others
            if(i>=2)dp[i][j]+=((j*(i-1))*dp[i-2][j-1])%mod;//place up-down choose (i,j1),(i2,j1) and move others
            dp[i][j]%=mod;
        }
    }
    printf("%lld",(dp[n][m]-1+mod)%mod);
    return 0;
}

Compilation message (stderr)

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

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