結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:16:03
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,933 bytes
コンパイル時間 157 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 145,164 KB
最終ジャッジ日時 2025-03-20 21:17:22
合計ジャッジ時間 29,070 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    Q = int(input[ptr])
    ptr += 1
    K_list = list(map(int, input[ptr:ptr+Q]))
    ptr += Q

    # Preprocess left and right cumulative HP and enemies
    left_cum_hp = [[] for _ in range(N)]
    left_cum_enemy = [[] for _ in range(N)]
    right_cum_hp = [[] for _ in range(N)]
    right_cum_enemy = [[] for _ in range(N)]

    for i in range(N):
        # Left direction (i-1, i-2, ...)
        current_hp = 0
        current_enemy = 0
        for j in range(i-1, -1, -1):
            current_hp += A[j]
            current_enemy += 1 if S[j] == 'E' else 0
            left_cum_hp[i].append(current_hp)
            left_cum_enemy[i].append(current_enemy)
        # Right direction (i+1, i+2, ...)
        current_hp = 0
        current_enemy = 0
        for j in range(i+1, N):
            current_hp += A[j]
            current_enemy += 1 if S[j] == 'E' else 0
            right_cum_hp[i].append(current_hp)
            right_cum_enemy[i].append(current_enemy)

    # Process each query
    for K in K_list:
        max_enemy = 0
        for i in range(N):
            # Left direction processing
            is_enemy = S[i] == 'E'
            required = A[i]
            if K < required:
                left_enemy = 0
            else:
                rem = K - required
                current_enemy = 1 if is_enemy else 0
                cum_hp = left_cum_hp[i]
                cum_enemy = left_cum_enemy[i]
                if not cum_hp:
                    left_enemy = current_enemy
                else:
                    # Find the maximum k where cum_hp[k] <= rem
                    # Using bisect_right
                    idx = bisect.bisect_right(cum_hp, rem)
                    sum_e = cum_enemy[idx-1] if idx > 0 else 0
                    left_enemy = current_enemy + sum_e
            # Check max
            if left_enemy > max_enemy:
                max_enemy = left_enemy

            # Right direction processing
            is_enemy = S[i] == 'E'
            required = A[i]
            if K < required:
                right_enemy = 0
            else:
                rem = K - required
                current_enemy = 1 if is_enemy else 0
                cum_hp = right_cum_hp[i]
                cum_enemy = right_cum_enemy[i]
                if not cum_hp:
                    right_enemy = current_enemy
                else:
                    idx = bisect.bisect_right(cum_hp, rem)
                    sum_e = cum_enemy[idx-1] if idx >0 else 0
                    right_enemy = current_enemy + sum_e
            # Check max
            if right_enemy > max_enemy:
                max_enemy = right_enemy
        print(max_enemy)
    print()

if __name__ == "__main__":
    main()
0