結果
問題 | No.2553 Holidays |
ユーザー |
![]() |
提出日時 | 2023-11-21 19:23:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,175 bytes |
コンパイル時間 | 471 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 78,336 KB |
最終ジャッジ日時 | 2024-09-26 10:20:35 |
合計ジャッジ時間 | 5,197 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 WA * 31 |
ソースコード
def solve(n, m, s):# o---x or x---o# o---o# x---x# がそれぞれ長さいくつが何個あるか数えるtype_0 = [0] * (n + 1)type_1 = [0] * (n + 1)type_2 = [0] * (n + 1)left = "x"c = 0res = 0xc = 0for i in range(n + 1):if i < n:a = s[i]if a == "x":xc += 1else:a = "x"if a == "o":res += 1if a == "-":c += 1else:if a == "x" and left == "x":type_2[c] += 1elif a == "o" and left == "o":type_1[c] += 1else:type_0[c] += 1c = 0left = a# そもそも休みres += type_1[1]# print(res)# print(type_0)# print(type_1)# print(type_2)# 貪欲mm = mfor i in range(3, n + 1, 2):d = min(mm // (i // 2), type_1[i])res += i * dmm -= d * (i // 2)if d < type_1[i]:res += 2 * mmmm = 0break# 2倍増えるところtwos = 0for i in range(2, n + 1, 2):twos += type_1[i] * (i // 2)for i in range(n + 1):twos += type_0[i] * (i // 2)# print(twos)if mm > twos:res += 2 * twosmm -= twoselse:res += 2 * mmmm = 0# 2倍弱増えるところfor i in range(n, 2, -1):d = min(mm // ((i + 1) // 2), type_2[i])res += i * dmm -= d * ((i + 1) // 2)if d < type_2[i]:res += 2 * mm - 1mm = 0break# それでも余った場合res_max = n - xcres = min(res + mm, res_max)# print(res)return resdef main():n, m = map(int, input().split())s = input()res = solve(n, m, s)print(res)def test():assert solve(8, 2, "x-o----x") == 5assert solve(20, 5, "xo--x-o--o--------ox") == 14assert solve(5, 0, "xo-ox") == 3assert solve(20, 20, "xo--x-o--o--------ox") == 17assert solve(5, 5, "xo-ox") == 3if __name__ == "__main__":test()main()