結果

問題 No.1139 Slime Race
ユーザー lam6er
提出日時 2025-03-31 17:51:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 528 ms / 2,000 ms
コード長 1,665 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 118,884 KB
最終ジャッジ日時 2025-03-31 17:52:33
合計ジャッジ時間 7,059 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

def compute_f(T, N, x, v):
    if N == 0:
        return 0
    active_t_start = 0
    active_speed = v[0]
    active_x_start = x[0]
    active_contrib = 0
    merged_contrib = 0
    non_merged_contrib = 0
    
    for i in range(1, N):
        xi = x[i]
        vi = v[i]
        
        denominator = vi - active_speed
        if denominator >= 0:
            collision_time = float('inf')
        else:
            numerator = (active_x_start - xi) - active_speed * active_t_start
            collision_time = numerator / denominator
        
        if collision_time > T or collision_time < active_t_start:
            non_merged_contrib += vi * T
        else:
            active_contrib += active_speed * (collision_time - active_t_start)
            merged_contrib += vi * collision_time
            
            active_t_start = collision_time
            active_x_start = active_x_start + active_speed * (collision_time - active_t_start)
            active_speed += vi
    
    active_contrib += active_speed * (T - active_t_start)
    total = active_contrib + merged_contrib + non_merged_contrib
    return total

def find_min_T(N, D, x, v):
    low = 0
    high = 2 * 10**18  # A sufficiently large upper bound
    
    while low < high:
        mid = (low + high) // 2
        current_f = compute_f(mid, N, x, v)
        if current_f >= D:
            high = mid
        else:
            low = mid + 1
    return low

# Read input
import sys
input = sys.stdin.read().split()
idx = 0
N = int(input[idx])
idx +=1
D = int(input[idx])
idx +=1
x = list(map(int, input[idx:idx+N]))
idx +=N
v = list(map(int, input[idx:idx+N]))

print(find_min_T(N, D, x, v))
0