oj.uz

Submission #813948

# Submission time Handle Problem Language Result Execution time Memory
813948 2023-08-08T04:42:34 Z devariaota Tents (JOI18_tents) C++17
48 / 100
 2000 ms 88048 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 12 ms 852 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 38 ms 1748 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 12 ms 852 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 38 ms 1748 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Correct 7 ms 468 KB Output is correct
15 Execution timed out 2081 ms 88048 KB Time limit exceeded
16 Halted 0 ms 0 KB -