結果

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

ソースコード

diff # 

def main():
    import sys
    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
    
    people = []
    sum_w = 0
    for _ in range(M):
        x = int(input[ptr])
        ptr += 1
        w = int(input[ptr])
        ptr += 1
        people.append((x, w))
        sum_w += w
    
    # Check c=0 case
    if all(s <= ai for ai in a for s in [sum_w]):
        print(0)
        return
    
    # Check if even when c is infinity (each contributes to x_j only)
    sum_x = [0] * (N + 2)  # 1-based
    for x, w in people:
        sum_x[x] += w
    for i in range(1, N+1):
        if sum_x[i] > a[i-1]:
            print(-1)
            return
    
    max_w = max(w for x, w in people)
    low = 1
    high = max_w
    answer = -1
    
    while low <= high:
        mid = (low + high) // 2
        delta_a = [0] * (N + 2)
        delta_b = [0] * (N + 2)
        
        for x, w in people:
            c = mid
            d = w // c
            # Left interval [x-d, x]
            L = x - d
            R = x
            L = max(1, L)
            R = min(R, N)
            if L <= R:
                a_val = w - c * x
                b_val = c
                delta_a[L] += a_val
                delta_a[R + 1] -= a_val
                delta_b[L] += b_val
                delta_b[R + 1] -= b_val
            # Right interval [x+1, x+d]
            L = x + 1
            R = x + d
            L = max(1, L)
            R = min(R, N)
            if L <= R:
                a_val = w + c * x
                b_val = -c
                delta_a[L] += a_val
                delta_a[R + 1] -= a_val
                delta_b[L] += b_val
                delta_b[R + 1] -= b_val
        
        # Compute prefix sums and check
        current_a = 0
        current_b = 0
        valid = True
        for i in range(1, N + 1):
            current_a += delta_a[i]
            current_b += delta_b[i]
            load = current_a + current_b * 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