oj.uz

Submission #220243

# Submission time Handle Problem Language Result Execution time Memory
220243 2020-04-07T12:27:41 Z rama_pang Tents (JOI18_tents) C++14
100 / 100
 239 ms 35712 KB 
#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int INV2 = (MOD + 1) / 2; // modular inverse of 2

int ADD() { return 0; }
int MUL() { return 1; }

template<typename... Tail>
int ADD(int Head, Tail... T) {
  return (Head += ADD(T...)) >= MOD ? Head - MOD : Head;
}

template<typename... Tail>
int MUL(int Head, Tail... T) {
  return 1ll * Head * MUL(T...) % MOD;
}

template<typename... Tail>
void RADD(int &Head, Tail... T) {
  Head = ADD(Head, T...);
}

int PartialSolutionDP(int N, int M) { // solution in O(N^3)
  vector<vector<int>> dp, nxt_dp;
  dp = nxt_dp = vector<vector<int>>(M + 2, vector<int>(M + 2, 0)); // [free_column][unmatched_tent]
  dp[M][0] = 1;

  for (int row = 0; row < N; row++) {
    for (int free_column = 0; free_column <= M; free_column++) {
      for (int unmatched_tent = 0; unmatched_tent <= M; unmatched_tent++) {
        int cur = dp[free_column][unmatched_tent];

        // place 2 tents
        if (free_column >= 2) {
          RADD(nxt_dp[free_column - 2][unmatched_tent], MUL(free_column, free_column - 1, cur, INV2));
        }

        // place 1 tent by itself
        if (free_column >= 1) {
          RADD(nxt_dp[free_column - 1][unmatched_tent + 1], MUL(free_column, cur));
        }

        // place 1 tent adjacent to an unmatched tent
        if (unmatched_tent >= 1) {
          RADD(nxt_dp[free_column][unmatched_tent - 1], MUL(unmatched_tent, cur));
        }

        // place no tents
        RADD(nxt_dp[free_column][unmatched_tent], cur);
      }
    }

    swap(dp, nxt_dp);
    nxt_dp = vector<vector<int>>(M + 1, vector<int>(M + 1, 0));
  }

  vector<int> POW4(M + 1);
  POW4[0] = 1;
  for (int i = 1; i <= M; i++) {
    POW4[i] = MUL(POW4[i - 1], 4);
  }

  int res = 0;
  for (int free_column = 0; free_column <= M; free_column++) {
    for (int unmatched_tent = 0; unmatched_tent <= M; unmatched_tent++) {
      RADD(res, MUL(POW4[unmatched_tent], dp[free_column][unmatched_tent])); // each unmatched tent can be placd in 4 directions
    }
  }

  return (res - 1 + MOD) % MOD; // decrease 1 (the empty grid placement)
}

int Solve(int N, int M) { // full solution in O(N^2)
  vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0)); // dp[current_row][free_column]

  dp[N][M] = 1;
  for (int row = N; row > 0; row--) {
    for (int free_column = 0; free_column <= M; free_column++) {
      // Place 0 tent.
      RADD(dp[row - 1][free_column], dp[row][free_column]);

      // Place 1 tent in the current row, there are 4 * free_column ways to do it.
      if (free_column >= 1) {
        RADD(dp[row - 1][free_column - 1], MUL(free_column, 4, dp[row][free_column]));
      }

      // Place 2 tents with the same row, there are col * (col - 1) / 2 ways to do it. 
      // Afterwards, the number of free columns decreased by 2.
      if (free_column >= 2) {
        RADD(dp[row - 1][free_column - 2], MUL(free_column, free_column - 1, dp[row][free_column], INV2));
      }

      // Place 2 tents with the same column, where one of them is in the current row.
      // Afterwards, there exists a row later on where we cannot place anything, so
      // we can safely assume it is not there. There are free_col ways to choose a column,
      // and N - 1 ways to pick the other pair (the row must be yet to be processed).
      if (row >= 2 && free_column >= 1) {
        RADD(dp[row - 2][free_column - 1], MUL(free_column, row - 1, dp[row][free_column]));
      }
    }
  }

  int res = 0;
  for (int col = 0; col <= M; col++) {
    RADD(res, dp[0][col]);
  }

  return (res - 1 + MOD) % MOD; // decrease 1 for empty grid configuration
}

int main() {
  int N, M;
  cin >> N >> M;
  cout << Solve(N, M) << "\n";
  return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 7 ms 640 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 7 ms 640 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 147 ms 22400 KB Output is correct
16 Correct 15 ms 1664 KB Output is correct
17 Correct 38 ms 5248 KB Output is correct
18 Correct 45 ms 6400 KB Output is correct
19 Correct 181 ms 26104 KB Output is correct
20 Correct 141 ms 20736 KB Output is correct
21 Correct 95 ms 13864 KB Output is correct
22 Correct 94 ms 13696 KB Output is correct
23 Correct 67 ms 7928 KB Output is correct
24 Correct 239 ms 35712 KB Output is correct
25 Correct 181 ms 26496 KB Output is correct
26 Correct 208 ms 30584 KB Output is correct
27 Correct 226 ms 34296 KB Output is correct