Submission #114019

#	Time	Username	Problem	Language	Result	Execution time	Memory
114019		shayan_p	Tents (JOI18_tents)	C++14	100 / 100	165 ms	35676 KiB

tents

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=3010,mod=1e9+7;
const ll inf=1e18;

int dp[maxn][maxn];

int C(int n){
    if(n<2) return 0;
    return (1ll*n*(n-1) /2) %mod;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;cin>>n>>m;
    dp[0][0]=1;
    for(int j=1;j<=m;j++){
	dp[0][j]=1;
	dp[1][j]=(C(j) + 4*j + 1) %mod;
    }
    for(int i=1;i<=n;i++){
	dp[i][0]=1;
	dp[i][1]=(C(i) + 4*i + 1) %mod;
    }
    for(int i=2;i<=n;i++){
	for(int j=2;j<=m;j++){
	    dp[i][j]=(1ll*C(j)*dp[i-1][j-2] + 1ll*(i-1)*(j)*dp[i-2][j-1] + 4ll*j*dp[i-1][j-1] + 1ll*dp[i-1][j] )%mod;
	}
    }
    int ans=dp[n][m]-1;
    if(ans<0) ans+=mod;
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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