結果

問題 No.1008 Bench Craftsman
ユーザー qqqqqqqq
提出日時 2020-03-26 18:36:40
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 362 ms / 2,000 ms
コード長 1,192 bytes
コンパイル時間 329 ms
コンパイル使用メモリ 82,784 KB
実行使用メモリ 120,800 KB
最終ジャッジ日時 2025-01-02 02:56:25
合計ジャッジ時間 8,591 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

n,m = map(int, input().split())
a = list(map(int, input().split()))
xw = []
for i in range(m):
    x,w = map(int, input().split())
    x -= 1
    xw.append([x,w])

def check(c):
    a_imos = [0]*(n+1)
    b_imos = [0]*(n+1)
    for x,w in xw:
        if c == 0:
            b_imos[0] += w
            b_imos[-1] -= w
            continue
        # xより大きい方
        right = min(n-1, (w+c*x)//c)
        if x<right:
            a_imos[x+1] += -c
            a_imos[right+1] -= -c
            b_imos[x+1] += w+c*x
            b_imos[right+1] -= w+c*x
        left = max(0, -(-(-w+c*x)//c))
        # x以下
        a_imos[left] += c
        a_imos[x+1] -= c
        b_imos[left] += w-c*x
        b_imos[x+1] -= w-c*x
    for i in range(n):
        s = i*a_imos[i] + b_imos[i]
        if s >= a[i]:
            return False
        a_imos[i+1] += a_imos[i]
        b_imos[i+1] += b_imos[i]
    return True

left = -1
right = 10**6

if not check(10**10):
    print(-1)
    exit()
while right-left > 1:
    mid = (right+left)//2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)
0