Submission #529763

# Submission time Handle Problem Language Result Execution time Memory
529763 2022-02-23T15:38:31 Z Alex_tz307 Tents (JOI18_tents) C++17
100 / 100
97 ms 35656 KB
#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;

void addSelf(int &x, const int &y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  }
}

int add(int x, const int &y) {
  addSelf(x, y);
  return x;
}

void multSelf(int &x, const int &y) {
  x = (int64_t)x * y % mod;
}

int mult(int x, const int &y) {
  multSelf(x, y);
  return x;
}

void testCase() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> dp(n + 1, vector<int>(m + 1, 1));
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      dp[i][j] = dp[i - 1][j]; /// nu pun nimic pe linia asta
      if (j >= 1) { /// pun ceva doar pe linia asta, apoi tai linia si coloana
        addSelf(dp[i][j], mult(dp[i - 1][j - 1], j * 4));
      }
      if (j >= 2) { /// pun 2 chestii pe linia asta, apoi tai linia si cele 2 coloane
        addSelf(dp[i][j], mult(dp[i - 1][j - 2], j * (j - 1) / 2));
      }
      if (i >= 2 && j >= 1) { /// pun ceva si pe linia asta si pe o linie anterioara
        addSelf(dp[i][j], mult(dp[i - 2][j - 1], j * (i - 1)));
      }
    }
  }
  cout << add(dp[n][m], mod - 1) << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 440 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 440 KB Output is correct
15 Correct 60 ms 22328 KB Output is correct
16 Correct 5 ms 1612 KB Output is correct
17 Correct 14 ms 5196 KB Output is correct
18 Correct 57 ms 6348 KB Output is correct
19 Correct 70 ms 25932 KB Output is correct
20 Correct 57 ms 20684 KB Output is correct
21 Correct 38 ms 13772 KB Output is correct
22 Correct 37 ms 13588 KB Output is correct
23 Correct 21 ms 7756 KB Output is correct
24 Correct 97 ms 35656 KB Output is correct
25 Correct 71 ms 26528 KB Output is correct
26 Correct 87 ms 30308 KB Output is correct
27 Correct 96 ms 34268 KB Output is correct