Submission #814029

# Submission time Handle Problem Language Result Execution time Memory
814029 2023-08-08T05:08:05 Z kebine Tents (JOI18_tents) C++17
100 / 100
132 ms 141408 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]=1;
    for(int i=1; i<=n; i++) dp[i][0]=1;
    for(int j=1; j<=m; j++) dp[0][j]=1;
    for(int i=1; i<=n; i++) {
      for(int j=1; j<=m; j++) {
          if(i>=2) dp[i][j]=(dp[i][j]+i*(i-1)/2*dp[i-2][j-1])%MOD;
          if(j>=2) dp[i][j]=(dp[i][j]+i*(j-1)*dp[i-1][j-2])%MOD;
          dp[i][j]=(dp[i][j]+4LL*i*dp[i-1][j-1]%MOD)%MOD;
          dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;
    }
    }
    cout << dp[n][m]-1 << '\n';
    return 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 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
# 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 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 77 ms 88088 KB Output is correct
16 Correct 6 ms 5972 KB Output is correct
17 Correct 22 ms 19916 KB Output is correct
18 Correct 26 ms 24660 KB Output is correct
19 Correct 92 ms 102620 KB Output is correct
20 Correct 73 ms 82060 KB Output is correct
21 Correct 55 ms 54168 KB Output is correct
22 Correct 53 ms 53444 KB Output is correct
23 Correct 31 ms 29872 KB Output is correct
24 Correct 123 ms 141408 KB Output is correct
25 Correct 99 ms 105016 KB Output is correct
26 Correct 132 ms 120568 KB Output is correct
27 Correct 129 ms 136004 KB Output is correct