結果
問題 | No.1008 Bench Craftsman |
ユーザー |
![]() |
提出日時 | 2020-03-06 22:39:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 185,376 KB |
最終ジャッジ日時 | 2024-10-14 09:00:11 |
合計ジャッジ時間 | 8,644 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#!/usr/bin/env python3 # %% import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines import itertools # %% N, M = map(int, readline().split()) A = list(map(int, readline().split())) m = map(int, read().split()) XW = tuple(zip(m, m)) # %% def calc_cost(N, c, XW): B1_d = [0] * (N + 1) B0_d = [0] * (N + 1) for x, w in XW: x -= 1 L = x - (w + c - 1) // c + 1 if L < 0: L = 0 const_term = w - c * x B1_d[L] += c B0_d[L] += const_term B1_d[x + 1] -= c B0_d[x + 1] -= const_term R = x + (w + c - 1) // c - 1 const_term = w + c * x if R >= N: R = N - 1 B1_d[x + 1] -= c B0_d[x + 1] += const_term B1_d[R + 1] += c B0_d[R + 1] -= const_term B0 = list(itertools.accumulate(B0_d))[:-1] B1 = list(itertools.accumulate(B1_d))[:-1] cost = [a * i + b for i, (a, b) in enumerate(zip(B1, B0))] return cost def test(c): if c == 0: return sum(w for x, w in XW) <= min(A) cost = calc_cost(N, c, XW) return all(x < a for a, x in zip(A, cost)) # %% left = -1 right = 10 ** 5 + 10 while left + 1 < right: mid = (left + right) // 2 if test(mid): right = mid else: left = mid if right > 10 ** 5: print(-1) else: print(right)