Submission #82379

#	Time	Username	Problem	Language	Result	Execution time	Memory
82379		MrTEK	Tents (JOI18_tents)	C++14	100 / 100	361 ms	36484 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 3e3 + 5;
const int mod = 1e9 + 7;

int n,m,dp[N][N];

inline int mul(int x,int y) {
  return (ll) x * y % mod;
}

inline int add(int x,int y) {
  return (x + y) % mod;
}

int f(int x,int y) {
  int &res = dp[x][y];
  if (res != -1)
    return res;
  if (x == 0 || y == 0)
    return 1;
  res = f(x - 1,y);
  if (y >= 2)
    res = add(res,mul(f(x - 1,y - 2),y * (y - 1) / 2));
  if (y >= 1)
    res = add(res,mul(f(x - 1,y -1),y * 4));
  if (x >= 2 && y >= 1)
    res = add(res,mul(f(x - 2,y - 1),mul(y,x - 1)));
  return res;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m;
  memset(dp,-1,sizeof dp);
  cout << f(n,m) - 1 << endl;
}

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