提出 #65380292

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
template <typename T>
using vc = vector<T>;

#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

void solve() {
  ll H, W;
  cin >> H >> W;
  string S;
  cin >> S;
  ll N = S.size();

  // prefix sum to count D, R
  vc<int> D(N + 1), R(N + 1);
  FOR(i, N) D[i + 1] = D[i] + (S[i] == 'D');
  FOR(i, N) R[i + 1] = R[i] + (S[i] == 'R');

  ll ANS = 0;
  FOR(n, H + W - 1) {
    ll D1 = D[n], D2 = D[N] - D[n];
    ll R1 = R[n], R2 = R[N] - R[n];
    // FOR(x, n + 1) {
    //   ll y = n - x;
    //   if (D1 <= x && x <= H - 1 - D2 && R1 <= y && y <= W - 1 - R2) ++ANS;
    // }
    ll mi = max(D1, n - W + 1 + R2);
    ll ma = min(H - 1 - D2, n - R1);
    ANS += ma - mi + 1;
  }
  cout << ANS << "\n";
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int T;
  cin >> T;
  FOR(T) solve();
}

提出情報

提出日時
問題 A - Union of Grid Paths
ユーザ maspy
言語 C++ 20 (gcc 12.2)
得点 400
コード長 1136 Byte
結果 AC
実行時間 9 ms
メモリ 6852 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 400 / 400
結果
AC × 1
AC × 56
セット名 テストケース
Sample 01_sample_01.txt
All 01_sample_01.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 02_small_06.txt, 02_small_07.txt, 02_small_08.txt, 02_small_09.txt, 02_small_10.txt, 03_mid_01.txt, 03_mid_02.txt, 03_mid_03.txt, 03_mid_04.txt, 03_mid_05.txt, 04_max_01.txt, 04_max_02.txt, 04_max_03.txt, 04_max_04.txt, 04_max_05.txt, 04_max_06.txt, 04_max_07.txt, 04_max_08.txt, 04_max_09.txt, 04_max_10.txt, 04_max_11.txt, 04_max_12.txt, 04_max_13.txt, 04_max_14.txt, 04_max_15.txt, 04_max_16.txt, 04_max_17.txt, 04_max_18.txt, 04_max_19.txt, 04_max_20.txt, 04_max_21.txt, 04_max_22.txt, 04_max_23.txt, 04_max_24.txt, 04_max_25.txt, 04_max_26.txt, 04_max_27.txt, 04_max_28.txt, 04_max_29.txt, 04_max_30.txt, 04_max_31.txt, 04_max_32.txt, 04_max_33.txt, 04_max_34.txt, 04_max_35.txt, 04_max_36.txt, 04_max_37.txt, 04_max_38.txt, 04_max_39.txt, 04_max_40.txt
ケース名 結果 実行時間 メモリ
01_sample_01.txt AC 1 ms 3416 KiB
02_small_01.txt AC 9 ms 3472 KiB
02_small_02.txt AC 9 ms 3448 KiB
02_small_03.txt AC 9 ms 3392 KiB
02_small_04.txt AC 9 ms 3604 KiB
02_small_05.txt AC 9 ms 3496 KiB
02_small_06.txt AC 9 ms 3492 KiB
02_small_07.txt AC 9 ms 3540 KiB
02_small_08.txt AC 9 ms 3608 KiB
02_small_09.txt AC 9 ms 3472 KiB
02_small_10.txt AC 9 ms 3540 KiB
03_mid_01.txt AC 3 ms 3556 KiB
03_mid_02.txt AC 3 ms 3548 KiB
03_mid_03.txt AC 3 ms 3476 KiB
03_mid_04.txt AC 3 ms 3548 KiB
03_mid_05.txt AC 3 ms 3452 KiB
04_max_01.txt AC 4 ms 6740 KiB
04_max_02.txt AC 4 ms 6680 KiB
04_max_03.txt AC 4 ms 6852 KiB
04_max_04.txt AC 4 ms 6844 KiB
04_max_05.txt AC 5 ms 6684 KiB
04_max_06.txt AC 4 ms 6676 KiB
04_max_07.txt AC 4 ms 6788 KiB
04_max_08.txt AC 4 ms 6780 KiB
04_max_09.txt AC 4 ms 6752 KiB
04_max_10.txt AC 4 ms 6780 KiB
04_max_11.txt AC 4 ms 6784 KiB
04_max_12.txt AC 4 ms 6760 KiB
04_max_13.txt AC 4 ms 6684 KiB
04_max_14.txt AC 4 ms 6736 KiB
04_max_15.txt AC 4 ms 6824 KiB
04_max_16.txt AC 5 ms 6676 KiB
04_max_17.txt AC 4 ms 6780 KiB
04_max_18.txt AC 4 ms 6612 KiB
04_max_19.txt AC 4 ms 6676 KiB
04_max_20.txt AC 4 ms 6848 KiB
04_max_21.txt AC 4 ms 6764 KiB
04_max_22.txt AC 4 ms 6824 KiB
04_max_23.txt AC 4 ms 6772 KiB
04_max_24.txt AC 4 ms 6748 KiB
04_max_25.txt AC 4 ms 6756 KiB
04_max_26.txt AC 4 ms 6756 KiB
04_max_27.txt AC 4 ms 6848 KiB
04_max_28.txt AC 4 ms 6788 KiB
04_max_29.txt AC 4 ms 6784 KiB
04_max_30.txt AC 4 ms 6776 KiB
04_max_31.txt AC 4 ms 6780 KiB
04_max_32.txt AC 4 ms 6676 KiB
04_max_33.txt AC 4 ms 6780 KiB
04_max_34.txt AC 4 ms 6688 KiB
04_max_35.txt AC 4 ms 6772 KiB
04_max_36.txt AC 4 ms 6816 KiB
04_max_37.txt AC 4 ms 6772 KiB
04_max_38.txt AC 4 ms 6752 KiB
04_max_39.txt AC 4 ms 6780 KiB
04_max_40.txt AC 4 ms 6840 KiB