結果

問題 No.1008 Bench Craftsman
ユーザー lam6er
提出日時 2025-04-15 21:36:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,639 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,764 KB
実行使用メモリ 148,516 KB
最終ジャッジ日時 2025-04-15 21:37:53
合計ジャッジ時間 6,244 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 = []
    for _ in range(M):
        x = int(input[ptr])
        w = int(input[ptr+1])
        people.append((x, w))
        ptr += 2
    
    sum_w = sum(w for x, w in people)
    min_a = min(a)
    if sum_w <= min_a:
        print(0)
        return
    
    sum_xj = [0] * (N + 2)  # 1-based
    for x, w in people:
        sum_xj[x] += w
    
    possible = True
    for i in range(1, N + 1):
        if sum_xj[i] > a[i - 1]:
            possible = False
            break
    if not possible:
        print(-1)
        return
    
    max_w = max(w for x, w in people)
    low = 1
    high = max_w
    ans = -1
    
    while low <= high:
        mid = (low + high) // 2
        delta_S1 = [0] * (N + 2)
        coeff_delta = [0] * (N + 2)
        const_delta = [0] * (N + 2)
        
        for x, w in people:
            k = w // mid
            L = max(1, x - k)
            R = min(N, x + k)
            delta_S1[L] += w
            delta_S1[R + 1] -= w
            
            # Left interval [L, x]
            a_left = L
            b_left = x
            if a_left <= b_left:
                coeff_delta[a_left] -= 1
                coeff_delta[b_left + 1] += 1
                const_delta[a_left] += x
                const_delta[b_left + 1] -= x
            
            # Right interval [x, R]
            a_right = x
            b_right = R
            if a_right <= b_right:
                coeff_delta[a_right] += 1
                coeff_delta[b_right + 1] -= 1
                const_delta[a_right] -= x
                const_delta[b_right + 1] += x
        
        # Compute S1
        S1 = [0] * (N + 1)
        current_S1 = 0
        for i in range(1, N + 1):
            current_S1 += delta_S1[i]
            S1[i] = current_S1
        
        # Check feasibility
        feasible = True
        current_coeff = 0
        current_const = 0
        for i in range(1, N + 1):
            current_coeff += coeff_delta[i]
            current_const += const_delta[i]
            coeff_i = current_coeff
            const_i = current_const
            S2_i = coeff_i * i + const_i
            load = S1[i] - mid * S2_i
            if load > a[i - 1]:
                feasible = False
                break
        
        if feasible:
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    
    print(ans if ans != -1 else -1)

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