結果

問題 No.3320 yiwiwiy
コンテスト
ユーザー みうね
提出日時 2025-10-06 09:51:52
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,702 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 88,532 KB
最終ジャッジ日時 2025-10-31 18:53:11
合計ジャッジ時間 4,086 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other TLE * 1 -- * 72
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

def compute_P_from_layout(a, b, center_seq, d, e):
    """
    center_seq: list of chars, each either 'i' or 'w'
    a, b, d, e: counts of y(left), i(left), i(right), y(right)
    Returns exact P value for the full string:
      y^a i^b + center_seq + i^d y^e
    We use formula: P = a * e * sum_{positions p where center_seq[p]=='w'} (i_before(p) * i_after(p))
    where i_before(p) = b + (number of 'i' in center_seq before p)
          i_after(p)  = d + (number of 'i' in center_seq after p)
    """
    # precompute prefix counts of i in center_seq
    n = len(center_seq)
    pref_i = [0] * (n+1)
    for i,ch in enumerate(center_seq):
        pref_i[i+1] = pref_i[i] + (1 if ch == 'i' else 0)
    total_i_inside = pref_i[n]
    total = 0
    for pos,ch in enumerate(center_seq):
        if ch == 'w':
            i_before = b + pref_i[pos]
            i_after = d + (total_i_inside - pref_i[pos+1])
            total += i_before * i_after
    P = a * e * total
    return P

def build_center_sequence(i_b, w_b, W_rem, side): 
    """
    Build a specific center sequence given:
      - i_b, w_b: mandatory alternation pattern sizes (these form the alternating block of length 2*q+3)
      - W_rem: extra w's to place (all placed on 'side': 'left' or 'right')
    We return a list of chars representing the center sequence.
    Strategy: place extra w's on chosen side of the alternating block.
    The alternating block is: i w i w ... i  (length 2*q+3, i_b = q+2, w_b = q+1)
    """
    # build alternating block starting with 'i'
    center = []
    qb = i_b + w_b
    # construct alternating: i w i w ... end with i (i_b times and w_b times interleaved)
    # We will append as i, w, i, w, ... using counts
    ic = i_b
    wc = w_b
    turn_i = True
    while ic > 0 or wc > 0:
        if turn_i:
            if ic > 0:
                center.append('i'); ic -= 1
            else:
                # no i left, but maybe w remains; switch
                turn_i = not turn_i
                continue
        else:
            if wc > 0:
                center.append('w'); wc -= 1
            else:
                turn_i = not turn_i
                continue
        turn_i = not turn_i
    # put extra W_rem on left or right
    if W_rem > 0:
        if side == 'left':
            center = ['w'] * W_rem + center
        else:
            center = center + ['w'] * W_rem
    return center

def best_for_one_case(Y, I, W, A, B):
    # Edge quick checks
    # q maximum
    if I < 2 or W < 1:
        # cannot form even q=0 alternation? q=0 needs i_b=2,w_b=1, but q=0 is allowed if I>=2 and W>=1.
        # If I<2 or W<1, then q_max= -ve, but we still consider q=0 if possible.
        pass

    best_value = 0

    # choose a,e (split Y) candidates: floor and ceil
    a_candidates = [Y // 2]
    if Y - (Y // 2) != (Y // 2):
        # if not exactly half, include other split
        a_candidates.append(Y - (Y // 2))
    # make unique
    a_candidates = sorted(set([min(x, Y-x) for x in a_candidates] + a_candidates))
    # but we actually want all distinct a values in {floor(Y/2), ceil(Y/2)}
    a_candidates = sorted(set([Y//2, Y - Y//2]))

    # q range
    q_max = max(-1, min(I - 2, W - 1))
    if q_max < 0:
        q_range = [0]  # q=0 only feasible as "no contiguous iwiwi"
    else:
        q_range = list(range(0, q_max + 1))

    for q in q_range:
        i_b = q + 2
        w_b = q + 1
        if i_b > I or w_b > W:
            continue
        I_rem = I - i_b
        W_rem = W - w_b

        # candidate splits for b (left i outside central): try center vicinity
        b_base = I_rem // 2
        b_candidates = set([b_base, I_rem - b_base])
        # also try ±1 around center if in range
        for delta in (-1,1):
            v = b_base + delta
            if 0 <= v <= I_rem:
                b_candidates.add(v)

        for b in sorted(b_candidates):
            d = I_rem - b
            for a in a_candidates:
                e = Y - a
                # try both placements of W_rem: left or right of alternating block
                for side in ('left','right'):
                    center_seq = build_center_sequence(i_b, w_b, W_rem, side)
                    P = compute_P_from_layout(a, b, center_seq, d, e)
                    val = A * P + B * q
                    if val > best_value:
                        best_value = val
    return best_value

def solve():
    T = int(input().strip())
    out = []
    for _ in range(T):
        Y,I,W,A,B = map(int, input().split())
        ans = best_for_one_case(Y,I,W,A,B)
        out.append(str(ans))
    print("\n".join(out))

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