1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>
#define debug if (0)

int n, m;
std::vector<int> A, B;
const int inf = 1e9;

void input() {
  std::cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    int x;
    std::cin >> x;
    A.push_back(x);
  }
  for (int i = 1; i <= m; i++) {
    int x;
    std::cin >> x;
    B.push_back(x);
  }
}

void calc_dp() {
  std::vector<int> res(n + m + 1, 0);
  int found = 0;
  int target = (n * (n - 1) / 2 + n) *
               (m * (m - 1) / 2 +
                m); // dla wartosci dla ktorych to ma szanse
                    // zakonczy sie w tym stuleciu, to bedzie w zakresie inta

  std::vector<std::vector<std::vector<std::vector<int>>>> dp(
      n + 1,
      std::vector<std::vector<std::vector<int>>>(
          m + 1, std::vector<std::vector<int>>(2, std::vector<int>(2, inf))));

  std::vector<std::vector<int>> sum(n + 1, std::vector<int>(m + 1, 0));
  std::vector<std::vector<int>> last_sum(n + 1, std::vector<int>(m + 1, 0));

  auto mv = [](int &v, int x) {
    if (x < v)
      v = x;
  };

  int tmp;

  for (int k = 2; k <= n + m; k++) {
    if (found == target)
      break;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        // baza
        dp[i + 1][j][0][0] = dp[i + 1][j][0][1] = 1;
        dp[i][j + 1][1][0] = dp[i][j + 1][1][1] = 1;
        // reszta
        for (int x = i; x <= n; x++) {
          for (int y = j; y <= m; y++) {
            if (x + y - i - j <= 1)
              continue;

            dp[x][y][0][0] = dp[x][y][0][1] = dp[x][y][1][0] = dp[x][y][1][1] =
                inf;

            if (x - 1 >= i) {
              // a, -
              if (x - 2 >= i && A[x - 1] < A[x - 2] &&
                  dp[x - 1][y][0][1] < inf) {
                mv(dp[x][y][0][0], 2);
                goto ap;
              }
              if (y - 1 >= j && A[x - 1] < B[y - 1] &&
                  dp[x - 1][y][1][1] < inf) {
                mv(dp[x][y][0][0], 2);
                goto ap;
              }
              if (x - 2 >= i && A[x - 1] < A[x - 2] &&
                  dp[x - 1][y][0][0] + 1 <= k)
                mv(dp[x][y][0][0], dp[x - 1][y][0][0] + 1);
              if (y - 1 >= j && A[x - 1] < B[y - 1] &&
                  dp[x - 1][y][1][0] + 1 <= k)
                mv(dp[x][y][0][0], dp[x - 1][y][1][0] + 1);

            ap:

              // a, +
              if (x - 2 >= i && A[x - 1] > A[x - 2] &&
                  dp[x - 1][y][0][0] < inf) {
                mv(dp[x][y][0][1], 2);
                goto b;
              }
              if (y - 1 >= j && A[x - 1] > B[y - 1] &&
                  dp[x - 1][y][1][0] < inf) {
                mv(dp[x][y][0][1], 2);
                goto b;
              }
              if (x - 2 >= i && A[x - 1] > A[x - 2] &&
                  dp[x - 1][y][0][1] + 1 <= k)
                mv(dp[x][y][0][1], dp[x - 1][y][0][1] + 1);
              if (y - 1 >= j && A[x - 1] > B[y - 1] &&
                  dp[x - 1][y][1][1] + 1 <= k)
                mv(dp[x][y][0][1], dp[x - 1][y][1][1] + 1);
            }

          b:

            if (y - 1 >= j) {
              // b, -
              if (y - 2 >= j && B[y - 1] < B[y - 2] &&
                  dp[x][y - 1][1][1] < inf) {
                mv(dp[x][y][1][0], 2);
                goto bp;
              }
              if (x - 1 >= i && B[y - 1] < A[x - 1] &&
                  dp[x][y - 1][0][1] < inf) {
                mv(dp[x][y][1][0], 2);
                goto bp;
              }
              if (y - 2 >= j && B[y - 1] < B[y - 2] &&
                  dp[x][y - 1][1][0] + 1 <= k)
                mv(dp[x][y][1][0], dp[x][y - 1][1][0] + 1);
              if (x - 1 >= i && B[y - 1] < A[x - 1] &&
                  dp[x][y - 1][0][0] + 1 <= k)
                mv(dp[x][y][1][0], dp[x][y - 1][0][0] + 1);

            bp:

              // b, +
              if (y - 2 >= j && B[y - 1] > B[y - 2] && dp[x][y - 1][1][0] < inf)
                mv(dp[x][y][1][1], 2);
              if (x - 1 >= i && B[y - 1] > A[x - 1] && dp[x][y - 1][0][0] < inf)
                mv(dp[x][y][1][1], 2);
              if (y - 2 >= j && B[y - 1] > B[y - 2] &&
                  dp[x][y - 1][1][1] + 1 <= k)
                mv(dp[x][y][1][1], dp[x][y - 1][1][1] + 1);
              if (x - 1 >= i && B[y - 1] > A[x - 1] &&
                  dp[x][y - 1][0][1] + 1 <= k)
                mv(dp[x][y][1][1], dp[x][y - 1][0][1] + 1);
            }
          }
        }

        for (int x = i + 1; x <= n; x++) {
          for (int y = j + 1; y <= m; y++) {
            tmp = std::min(dp[x][y][0][0], dp[x][y][0][1]);
            tmp = std::min(tmp, dp[x][y][1][0]);
            tmp = std::min(tmp, dp[x][y][1][1]);
            // jest splot (i, j) -> (x-1, y-1)
            if (tmp < inf)
              sum[i][j]++;
          }
        }

        tmp = sum[i][j] - last_sum[i][j];
        res[k] += tmp;
        found += tmp;
      }
    }
    last_sum = sum;
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= m; j++)
        sum[i][j] = 0;
  }

  for (int i = 1; i <= n + m; i++)
    std::cout << res[i] << " ";
  std::cout << "\n";
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(NULL);
  input();
  calc_dp();
}