結果

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

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    M = int(input[ptr])
    ptr += 1
    a = list(map(int, input[ptr:ptr+N]))
    ptr += N
    sum_w = [0] * (N + 2)  # 1-based
    people = []
    max_w = 0
    for _ in range(M):
        x = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        people.append((x, w))
        sum_w[x] += w
        if w > max_w:
            max_w = w

    # Check impossible case
    for i in range(1, N+1):
        if sum_w[i] >= a[i-1]:
            print(-1)
            return

    # Check c=0 case
    total_w = sum(w for x, w in people)
    valid = True
    for ai in a:
        if total_w > ai:
            valid = False
            break
    if valid:
        print(0)
        return

    # Binary search
    low = 1
    high = max_w
    answer = -1

    while low <= high:
        mid = (low + high) // 2
        # Initialize difference arrays
        diff_A = [0] * (N + 2)  # 1-based to N, +2 for safety
        diff_B = [0] * (N + 2)

        for x, w in people:
            if mid == 0:
                continue  # handled earlier
            k = (w - 1) // mid
            # Left interval: x -k to x-1
            left_start = max(1, x - k)
            left_end = x - 1
            if left_start <= left_end:
                A = mid
                B = w - mid * x
                # Add to diff_A and diff_B
                diff_A[left_start] += A
                diff_A[left_end + 1] -= A
                diff_B[left_start] += B
                diff_B[left_end + 1] -= B
            # Right interval: x to x +k
            right_start = x
            right_end = min(N, x + k)
            if right_start <= right_end:
                A = -mid
                B = w + mid * x
                diff_A[right_start] += A
                diff_A[right_end + 1] -= A
                diff_B[right_start] += B
                diff_B[right_end + 1] -= B

        # Compute prefix sums
        A_total = 0
        B_total = 0
        valid = True
        for i in range(1, N+1):
            A_total += diff_A[i]
            B_total += diff_B[i]
            current_load = A_total * i + B_total
            if current_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