結果

問題 No.1008 Bench Craftsman
ユーザー lam6er
提出日時 2025-04-15 21:30:21
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,868 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 82,140 KB
実行使用メモリ 152,140 KB
最終ジャッジ日時 2025-04-15 21:33:17
合計ジャッジ時間 6,570 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx +=1
    M = int(data[idx])
    idx +=1
    a = list(map(int, data[idx:idx+N]))
    idx +=N
    x_list = []
    w_list = []
    sum_self = [0]*(N+2)  # 1-based
    sum_total =0
    max_wj =0
    for _ in range(M):
        x = int(data[idx])
        idx +=1
        w = int(data[idx])
        idx +=1
        x_list.append(x)
        w_list.append(w)
        sum_self[x] +=w
        sum_total +=w
        if w > max_wj:
            max_wj =w
    
    # Check sum_self
    for i in range(1, N+1):
        if sum_self[i] > a[i-1]:
            print(-1)
            return
    
    # Check sum_total
    valid = True
    for i in range(1, N+1):
        if sum_total > a[i-1]:
            valid = False
            break
    if valid:
        print(0)
        return
    
    # Binary search
    low =1
    high = max_wj
    answer = -1
    while low <= high:
        mid = (low + high) //2
        # Initialize delta arrays
        delta_A = [0]*(N+2)
        delta_B = [0]*(N+2)
        for j in range(M):
            x = x_list[j]
            w = w_list[j]
            c = mid
            d_max = w // c
            # Left range
            left_start = max(1, x - d_max)
            left_end = x
            if left_start <= left_end:
                A_left = w - c * x
                B_left = c
                delta_A[left_start] += A_left
                if left_end +1 <= N:
                    delta_A[left_end +1] -= A_left
                delta_B[left_start] += B_left
                if left_end +1 <= N:
                    delta_B[left_end +1] -= B_left
            # Right range
            right_start = x +1
            right_end = min(N, x + d_max)
            if right_start <= right_end:
                A_right = w + c * x
                B_right = -c
                delta_A[right_start] += A_right
                if right_end +1 <= N:
                    delta_A[right_end +1] -= A_right
                delta_B[right_start] += B_right
                if right_end +1 <= N:
                    delta_B[right_end +1] -= B_right
        # Compute sum_A and sum_B
        sum_A = [0]*(N+1)
        sum_B = [0]*(N+1)
        current_A =0
        current_B =0
        for i in range(1, N+1):
            current_A += delta_A[i]
            current_B += delta_B[i]
            sum_A[i] = current_A
            sum_B[i] = current_B
        # Check each i
        valid = True
        for i in range(1, N+1):
            load = sum_A[i] + sum_B[i] * i
            if load > a[i-1]:
                valid = False
                break
        if valid:
            answer = mid
            high = mid -1
        else:
            low = mid +1
    print(answer if answer !=-1 else -1)

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