Submission #813948

#	Time	Username	Problem	Language	Result	Execution time	Memory
813948		devariaota	Tents (JOI18_tents)	C++17	48 / 100	2081 ms	88048 KiB

tents

#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int MOD=1e9+7;
signed main() {
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int n, m; cin >> n >> m;
  vector<vector<int>> dp(n+1, vector<int>(m+1));
  vector<vector<int>> pre(n+1, vector<int>(m+1));
  dp[0][0]=pre[0][0]=1;
  for(int i=1; i<=n; i++) dp[i][0]=pre[i][0]=1;
  for(int j=1; j<=m; j++) dp[0][j]=pre[0][j]=1;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      for(int k=1; k<=m; k++) pre[i][j]+=dp[i][k];
      for(int k=1; k<=n; k++) pre[i][j]+=dp[k][j];
      if(i>=2) dp[i][j]=(dp[i][j]+i*(i-1)/2*dp[i-2][j-1]+pre[i-2][j-1])%MOD;
      if(j>=2) dp[i][j]=(dp[i][j]+i*(j-1)*dp[i-1][j-2]+pre[i-1][j-2])%MOD;
      dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
      dp[i][j]=(dp[i][j]+4LL*i*dp[i-1][j-1]%MOD)%MOD;
      if(i>=2) dp[i][j]=(dp[i][j]-pre[i-2][j-1]+MOD)%MOD;
      if(j>=2) dp[i][j]=(dp[i][j]-pre[i-1][j-2]+MOD)%MOD;
      pre[i][j]=(dp[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+MOD)%MOD;
    }
  }
  cout << dp[n][m]-1 << '\n';
  return 0;
}

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