Submission #529763

#	Time	Username	Problem	Language	Result	Execution time	Memory
529763		Alex_tz307	Tents (JOI18_tents)	C++17	100 / 100	97 ms	35656 KiB

tents

#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;
}

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