結果

問題 No.1008 Bench Craftsman
ユーザー lam6er
提出日時 2025-03-20 18:54:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,309 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 267,508 KB
最終ジャッジ日時 2025-03-20 18:55:59
合計ジャッジ時間 24,860 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    N, M = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().split()))
    sum_w = [0] * (N + 2)  # 1-based indexing
    people = []
    sum_total = 0

    for _ in range(M):
        x, w = map(int, sys.stdin.readline().split())
        people.append((x, w))
        sum_w[x] += w
        sum_total += w

    # Check if any section's sum_w exceeds a[i]
    for i in range(1, N + 1):
        if sum_w[i] > a[i - 1]:
            print(-1)
            return

    # Check if sum_total is less than or equal to all a[i]
    min_a = min(a)
    if sum_total <= min_a:
        print(0)
        return

    # Binary search for the minimum c
    low = 1
    high = 10**18
    answer = -1

    while low <= high:
        mid = (low + high) // 2
        a_coeff = [0] * (N + 2)
        b_coeff = [0] * (N + 2)

        for x, w in people:
            if mid == 0:
                continue
            d = (w - 1) // mid
            L = max(1, x - d)
            R_left = x
            R = min(N, x + d)

            # Left part [L, R_left]
            a_val = mid
            b_val = w - mid * x

            a_coeff[L] += a_val
            if R_left + 1 <= N:
                a_coeff[R_left + 1] -= a_val
            b_coeff[L] += b_val
            if R_left + 1 <= N:
                b_coeff[R_left + 1] -= b_val

            # Right part [x+1, R]
            start = x + 1
            if start > R:
                continue
            a_val_right = -mid
            b_val_right = w + mid * x

            a_coeff[start] += a_val_right
            if R + 1 <= N:
                a_coeff[R + 1] -= a_val_right
            b_coeff[start] += b_val_right
            if R + 1 <= N:
                b_coeff[R + 1] -= b_val_right

        # Calculate prefix sums and check
        current_a = 0
        current_b = 0
        valid = True
        for i in range(1, N + 1):
            current_a += a_coeff[i]
            current_b += b_coeff[i]
            total = current_a * i + current_b
            if total > 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