Submission #1034011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034011		vjudge1	Tents (JOI18_tents)	C++17	100 / 100	290 ms	139604 KiB

tents

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define all(v) begin(v), end(v)
#define pi pair<int, int>
#define vi vector<int>
using namespace std;
const ll mod=1e9+7, maxn = 3e3+3;
ll n, m, nn, mm, dp[maxn][maxn], dp2[maxn][maxn];
bool c[maxn][maxn], c2[maxn][maxn];
 
ll solve2(ll n,ll m){
    if(m==0) return 1;
    if(c2[n][m]) return dp2[n][m];
    c2[n][m]=true;

    dp2[n][m] = solve2(n,m-1);
    if(n>=1)dp2[n][m] += solve2(n-1,m-1)*n*4;
    if(n>=2)dp2[n][m] += solve2(n-2,m-1)*n*(n-1)/2;

    return dp2[n][m] = dp2[n][m]%mod;
}
 
ll solve(ll n,ll m){
    if(n==0) return solve2(nn-(mm-m)/2,m);
    if(c[n][m]) return dp[n][m];
    c[n][m]=true;

    dp[n][m] = solve(n-1,m);
    if(m>=2) dp[n][m] += solve(n-1,m-2)*m*(m-1)/2;

    return dp[n][m] = dp[n][m]%mod;    
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    nn=n, mm=m;
    cout << solve(n,m)-1;
    return 0;
}

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