結果

問題 No.1104 オンライン点呼
ユーザー qwewe
提出日時 2025-05-14 12:56:35
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,699 bytes
コンパイル時間 165 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 103,012 KB
最終ジャッジ日時 2025-05-14 12:58:51
合計ジャッジ時間 3,666 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 WA * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to read input faster
def get_ints():
    """Reads a line of space-separated integers from stdin."""
    return map(int, sys.stdin.readline().strip().split())

def get_list():
    """Reads a line of space-separated integers from stdin and returns as a list."""
    return list(map(int, sys.stdin.readline().strip().split()))

def solve():
    """Solves the online roll call problem."""
    
    # Read N and K from the first line of input
    N, K = get_ints()
    
    # Handle the base case where N=1.
    # If there's only one employee, they shout their number "1" at time 0.
    # The process ends immediately. Total time elapsed is 0.
    if N == 1:
        # We still need to read the A and B arrays to consume the input lines
        # according to the problem format, even though they are not used for N=1.
        A = get_list() 
        B = get_list() 
        print(0)
        return

    # Read the arrays A (upload times) and B (download times)
    # A[i] corresponds to A_{i+1}, B[i] corresponds to B_{i+1}
    A = get_list()
    B = get_list()

    # We will use dynamic programming with O(1) space complexity.
    # We need to keep track of the shout times for the previous two employees
    # to calculate the shout time for the current employee.
    
    # T_prev_prev stores the shout time of employee j-2 (T_{j-2})
    # T_prev stores the shout time of employee j-1 (T_{j-1})
    
    # Initialize the base cases:
    # Employee 1 shouts at time T_1 = 0.
    T_prev_prev = 0 

    # Employee 2 shouts when they hear employee 1.
    # Time to hear = T_1 + A_1 + B_2.
    # Since T_1 = 0, T_2 = A_1 + B_2.
    # Using 0-based indexing: T_2 = A[0] + B[1].
    # This requires N >= 2, which is guaranteed because we handled N=1 case.
    T_prev = A[0] + B[1]
    
    # If N=2, the last employee to shout is employee 2.
    # The total time is T_2.
    if N == 2:
        print(T_prev)
        return

    # Iterate to compute T_j for employees j = 3 to N.
    # The loop variable `j` represents the employee number (1-based index).
    for j in range(3, N + 1):
        # Calculate the time employee j shouts, T_j.
        # Employee j shouts at the minimum of two possible times based on conditions:
        # Condition 1: Hearing employee j-1. Time = T_{j-1} + A_{j-1} + B_j
        # Condition 2: K seconds after hearing employee j-2, if j-1 is not heard by then. Time = T_{j-2} + A_{j-2} + B_j + K
        
        # Convert to 0-based array indices:
        # Employee j corresponds to index j-1. B_j is B[j-1].
        # Employee j-1 corresponds to index j-2. A_{j-1} is A[j-2].
        # Employee j-2 corresponds to index j-3. A_{j-2} is A[j-3].
        
        # Calculate time based on Condition 1:
        # T_{j-1} is stored in T_prev. A_{j-1} is A[j-2]. B_j is B[j-1].
        time_cond1 = T_prev + A[j-2] + B[j-1]
        
        # Calculate time based on Condition 2:
        # T_{j-2} is stored in T_prev_prev. A_{j-2} is A[j-3]. B_j is B[j-1]. K is given.
        time_cond2 = T_prev_prev + A[j-3] + B[j-1] + K
        
        # T_j is the minimum of the two times.
        T_curr = min(time_cond1, time_cond2)
        
        # Update the DP states for the next iteration (to calculate T_{j+1}):
        # The current T_{j-1} (stored in T_prev) becomes the new T_{j-2} (stored in T_prev_prev).
        # The calculated T_j (stored in T_curr) becomes the new T_{j-1} (stored in T_prev).
        T_prev_prev = T_prev
        T_prev = T_curr

    # After the loop completes, T_prev holds the value of T_N,
    # which is the time the last employee (N) shouts.
    print(T_prev)

# Call the solve function to execute the solution logic
solve()
0