提出 #32179163 - AtCoder Regular Contest 109

コンテスト時間: 2020-11-28 21:00:00+0900 ~ 2020-11-28 23:00:00+0900 (120分) AtCoderホームへ戻る

提出 #32179163

ソースコード拡げる

#include <atcoder/modint>
#include <bits/stdc++.h>
#define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))

using namespace std;

template <class T> inline bool chmin(T &l, const T &r) {
  return l > r ? l = r, 1 : 0;
}

int dp[112345][2][2][2][3][2][2]; // idx, Wusd?, Busd?, chosen?,wbbbw, www, b

int solve(const string mp) {
  const int n = mp.size();
  const int INF = 1e8;
  int re = INF;
  rep(t, 2) {
    fill(dp[0][0][0][0][0][0], dp[n + 1][0][0][0][0][0], INF);
    dp[0][0][0][0][0][0][0] = 0;
    rep(i, n - 1) {
      rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
        if (isupper(mp[i]))
          dp[i][wusd][busd][0][j][k][l] = INF;
        dp[i][wusd][busd][1][j][k][l]++;
      }
      rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
        if (mp[i] % 2 == 1 - t && i && mp[i - 1] % 2 == t)
          chmin(dp[i][wusd][busd][1][1][k][l], dp[i][wusd][busd][1][j][k][l]);
        if (mp[i] % 2 == 1 - t && i + 1 < n && mp[i + 1] % 2 == t && j)
          chmin(dp[i][wusd][busd][1][2][k][l], dp[i][wusd][busd][1][j][k][l]);
        if (mp[i] % 2 == t && i && mp[i - 1] % 2 == t && i + 1 < n &&
            mp[i + 1] % 2 == t)
          chmin(dp[i][wusd][busd][1][j][1][l], dp[i][wusd][busd][1][j][k][l]);
        if (mp[i] % 2 == 1 - t)
          chmin(dp[i][wusd][busd][1][j][k][1], dp[i][wusd][busd][1][j][k][l]);
      }
      rep(wusd, 2) rep(busd, 2) rep(chosen, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
        chmin(dp[i + 1][wusd][busd][1][j][k][l],
              dp[i][wusd][busd][chosen][j][k][l]);
        chmin(dp[i + 1][wusd][busd][0][0][0][0], dp[i][wusd][busd][1][2][k][l]);
        chmin(dp[i + 1][1][busd][0][0][0][0], dp[i][0][busd][1][j][1][l]);
        chmin(dp[i + 1][wusd][1][0][0][0][0], dp[i][wusd][0][1][j][k][1]);
        chmin(dp[i + 1][wusd][busd][0][0][0][0], dp[i][wusd][busd][0][0][0][0]);
      }
    }
    rep(wusd, 2) rep(busd, 2) chmin(re, dp[n - 1][wusd][busd][0][0][0][0]);
  }
  return re;
}

int main() {
  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  rep(i, n) if (t[i] == 'o') s[i] = toupper(s[i]);
  cout << solve("www" + s + "bbb") << endl;
  return 0;
}

提出情報

提出日時	2022-06-03 20:24:59+0900
問題	F - 1D Kingdom Builder
ユーザ	nuip
言語	C++ (GCC 9.2.1)
得点	900
コード長	2203 Byte
結果	AC
実行時間	181 ms
メモリ	41468 KiB

コンパイルエラー

./Main.cpp: In function ‘int solve(std::string)’:
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘t’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:17:3: note: in expansion of macro ‘rep’
   17 |   rep(t, 2) {
      |   ^~~
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:20:5: note: in expansion of macro ‘rep’
   20 |     rep(i, n - 1) {
      |     ^~~
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘wusd’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:21:7: note: in expansion of macro ‘rep’
   21 |       rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
      |       ^~~
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘busd’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:21:20: note: in expansion of macro ‘rep’
   21 |       rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
      |                    ^~~
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘j’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:21:33: note: in expansion of macro ‘rep’
   21 |       rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
      |                                 ^~~
./Main.cpp:3:27: warning: unnecessary parentheses in declaration of ‘k’ [-Wparentheses]
    3 | #define rep(X, Y) for (int(X) = 0; (X) < (int)(Y); ++(X))
      |                           ^
./Main.cpp:21:43: note: in expansion of macro ‘rep’
   21 |       rep(wusd, 2) rep(busd, 2) rep(j, 3) rep(k, 2) rep(l, 2) {
      |                       ...

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

900 / 900

結果

× 4

× 67

セット名	テストケース
Sample	sample.txt, sample_2.txt, sample_3.txt, sample_4.txt
All	after_contest_1.txt, bDots.txt, bDots_2.txt, bDots_3.txt, bOnly.txt, bOnly_2.txt, blackLR.txt, black_-1.txt, black_0.txt, black_1.txt, center_3.txt, center_3_10.txt, center_3_10_2.txt, center_3_2.txt, center_3_3000.txt, center_3_3000_2.txt, center_3_500.txt, center_3_50000.txt, center_3_50000_2.txt, center_3_500_2.txt, center_5.txt, center_5_10.txt, center_5_10_2.txt, center_5_2.txt, center_5_3000.txt, center_5_3000_2.txt, center_5_500.txt, center_5_50000.txt, center_5_50000_2.txt, center_5_500_2.txt, center_7.txt, center_7_10.txt, center_7_10_2.txt, center_7_2.txt, center_7_3000.txt, center_7_3000_2.txt, center_7_500.txt, center_7_50000.txt, center_7_50000_2.txt, center_7_500_2.txt, raand.txt, raand_2.txt, raand_3.txt, raand_4.txt, raand_5.txt, random_1_1000.txt, random_1_50.txt, random_1_50000.txt, random_3_1000.txt, random_3_50.txt, random_3_50000.txt, random_5_1000.txt, random_5_50.txt, random_5_50000.txt, sample.txt, sample_2.txt, sample_3.txt, sample_4.txt, wDots.txt, wDots_2.txt, wDots_3.txt, wOnly.txt, wOnly_2.txt, whiteLR.txt, white_-1.txt, white_0.txt, white_1.txt

ケース名	結果	実行時間	メモリ
after_contest_1.txt	AC	6 ms	3512 KiB
bDots.txt	AC	178 ms	41404 KiB
bDots_2.txt	AC	176 ms	41444 KiB
bDots_3.txt	AC	177 ms	41412 KiB
bOnly.txt	AC	177 ms	41344 KiB
bOnly_2.txt	AC	176 ms	41240 KiB
blackLR.txt	AC	172 ms	41320 KiB
black_-1.txt	AC	169 ms	41400 KiB
black_0.txt	AC	168 ms	41368 KiB
black_1.txt	AC	168 ms	41316 KiB
center_3.txt	AC	12 ms	4596 KiB
center_3_10.txt	AC	107 ms	24844 KiB
center_3_10_2.txt	AC	104 ms	24416 KiB
center_3_2.txt	AC	107 ms	25268 KiB
center_3_3000.txt	AC	163 ms	37616 KiB
center_3_3000_2.txt	AC	147 ms	34120 KiB
center_3_500.txt	AC	108 ms	25336 KiB
center_3_50000.txt	AC	137 ms	30808 KiB
center_3_50000_2.txt	AC	90 ms	22464 KiB
center_3_500_2.txt	AC	143 ms	32924 KiB
center_5.txt	AC	121 ms	28560 KiB
center_5_10.txt	AC	164 ms	39000 KiB
center_5_10_2.txt	AC	165 ms	38788 KiB
center_5_2.txt	AC	53 ms	12868 KiB
center_5_3000.txt	AC	112 ms	25712 KiB
center_5_3000_2.txt	AC	106 ms	24856 KiB
center_5_500.txt	AC	161 ms	37824 KiB
center_5_50000.txt	AC	150 ms	34508 KiB
center_5_50000_2.txt	AC	162 ms	36532 KiB
center_5_500_2.txt	AC	96 ms	22536 KiB
center_7.txt	AC	85 ms	19588 KiB
center_7_10.txt	AC	175 ms	40880 KiB
center_7_10_2.txt	AC	119 ms	28384 KiB
center_7_2.txt	AC	61 ms	14648 KiB
center_7_3000.txt	AC	147 ms	34288 KiB
center_7_3000_2.txt	AC	148 ms	34272 KiB
center_7_500.txt	AC	108 ms	25128 KiB
center_7_50000.txt	AC	160 ms	36128 KiB
center_7_50000_2.txt	AC	178 ms	40348 KiB
center_7_500_2.txt	AC	110 ms	26116 KiB
raand.txt	AC	180 ms	41372 KiB
raand_2.txt	AC	175 ms	41296 KiB
raand_3.txt	AC	175 ms	41404 KiB
raand_4.txt	AC	181 ms	41372 KiB
raand_5.txt	AC	177 ms	41372 KiB
random_1_1000.txt	AC	162 ms	37124 KiB
random_1_50.txt	AC	111 ms	26180 KiB
random_1_50000.txt	AC	104 ms	24684 KiB
random_3_1000.txt	AC	174 ms	39500 KiB
random_3_50.txt	AC	112 ms	26028 KiB
random_3_50000.txt	AC	165 ms	37184 KiB
random_5_1000.txt	AC	141 ms	32064 KiB
random_5_50.txt	AC	167 ms	37716 KiB
random_5_50000.txt	AC	102 ms	24052 KiB
sample.txt	AC	2 ms	3576 KiB
sample_2.txt	AC	3 ms	3504 KiB
sample_3.txt	AC	2 ms	3628 KiB
sample_4.txt	AC	3 ms	3476 KiB
wDots.txt	AC	180 ms	41344 KiB
wDots_2.txt	AC	177 ms	41468 KiB
wDots_3.txt	AC	176 ms	41372 KiB
wOnly.txt	AC	176 ms	41028 KiB
wOnly_2.txt	AC	178 ms	41420 KiB
whiteLR.txt	AC	169 ms	41416 KiB
white_-1.txt	AC	169 ms	41392 KiB
white_0.txt	AC	168 ms	41392 KiB
white_1.txt	AC	170 ms	41420 KiB