結果

問題 No.935 う　し　た　ぷ　に　き　あ く ん 笑　ビ　－　ム
ユーザー lam6er
提出日時 2025-03-31 17:21:36
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,891 ms / 2,000 ms
コード長 2,332 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,640 KB
実行使用メモリ 144,988 KB
最終ジャッジ日時 2025-03-31 17:23:32
合計ジャッジ時間 35,566 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx +=1
    S = input[idx].strip()
    idx +=1
    A = list(map(int, input[idx:idx+N]))
    idx += N
    Q = int(input[idx])
    idx +=1
    K = list(map(int, input[idx:idx+Q]))
    
    # Preprocess left and right directions for each i
    left_damage = [[] for _ in range(N)]
    left_enemy = [[] for _ in range(N)]
    right_damage = [[] for _ in range(N)]
    right_enemy = [[] for _ in range(N)]
    
    for i in range(N):
        # Left direction (i, i-1, ..., 0)
        current_damage = 0
        current_enemies = 0
        l_damage = []
        l_enemy = []
        for j in range(i + 1):
            pos = i - j
            current_damage += A[pos]
            if S[pos] == 'E':
                current_enemies += 1
            l_damage.append(current_damage)
            l_enemy.append(current_enemies)
        left_damage[i] = l_damage
        left_enemy[i] = l_enemy
        
        # Right direction (i, i+1, ..., N-1)
        current_damage = 0
        current_enemies = 0
        r_damage = []
        r_enemy = []
        for j in range(N - i):
            pos = i + j
            current_damage += A[pos]
            if S[pos] == 'E':
                current_enemies += 1
            r_damage.append(current_damage)
            r_enemy.append(current_enemies)
        right_damage[i] = r_damage
        right_enemy[i] = r_enemy
    
    # Process each query
    results = []
    for k in K:
        max_e = 0
        for i in range(N):
            # Left direction
            ld = left_damage[i]
            pos = bisect.bisect_right(ld, k)
            if pos == 0:
                e_left = 0
            else:
                e_left = left_enemy[i][pos-1]
            
            # Right direction
            rd = right_damage[i]
            pos_r = bisect.bisect_right(rd, k)
            if pos_r == 0:
                e_right = 0
            else:
                e_right = right_enemy[i][pos_r-1]
            
            current_max = max(e_left, e_right)
            if current_max > max_e:
                max_e = current_max
        results.append(max_e)
    
    # Output all results
    sys.stdout.write('\n'.join(map(str, results)) + '\n')

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