Submission #65502553

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
  o << "{";
  for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
  return o << "}"; }
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
  return o << "(" << x.first << ", " << x.second << ")"; }
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif

const int N = 200200;
int n, m;
string s;
int pra[2 * N], dol[2 * N];
int a[N], b[N];

void solve() {
  cin >> n >> m >> s;
  pra[n + m - 2] = dol[n + m - 2] = 0;
  for (int i = n + m - 3; i >= 0; i--) {
    pra[i] = pra[i + 1];
    dol[i] = dol[i + 1];
    pra[i] += s[i] == 'R';
    dol[i] += s[i] == 'D';
  }
  rep(i, 0, n) a[i] = -1, b[i] = m;
  int x = 0, y = 0;
  rep(i, 0, n + m - 2) {
    a[x] = max(a[x], y);
    if (s[i] == 'D') {
      x++;
    } else if (s[i] == 'R') {
      y++;
    } else {
      if (y + pra[i + 1] < m - 1) y++;
      else x++;
    }
  }
  a[x] = max(a[x], m - 1);
  x = y = 0;
  rep(i, 0, n + m - 2) {
    b[x] = min(b[x], y);
    if (s[i] == 'D') {
      x++;
    } else if (s[i] == 'R') {
      y++;
    } else {
      if (x + dol[i + 1] < n - 1) x++;
      else y++;
    }
  }
  b[x] = min(b[x], m - 1);
  ll odp = 0;
  rep(i, 0, n) odp += a[i] - b[i] + 1;
  cout << odp << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
}

Submission Info

Judge Result