結果
問題 | No.913 木の燃やし方 |
ユーザー |
![]() |
提出日時 | 2023-03-16 06:40:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 937 ms / 3,000 ms |
コード長 | 1,724 bytes |
コンパイル時間 | 184 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 148,984 KB |
最終ジャッジ日時 | 2024-09-18 09:14:17 |
合計ジャッジ時間 | 28,469 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
import sysinput = sys.stdin.readlinefrom collections import *class CHT: #傾きの単調性と最小値クエリのxの単調性を仮定def __init__(self):self.q = deque([]) #直線群def f(self, f1, x): #直線f1のxの値return f1[0]*x+f1[1]def check(self, f1, f2, f3): #f2を削除しても良いかの判定return (f2[0]-f1[0])*(f3[1]-f2[1])>=(f2[1]-f1[1])*(f3[0]-f2[0])def add_line(self, a, b): #傾きa, 切片bの直線を追加while len(self.q)>=2 and self.check(self.q[-2], self.q[-1], (a, b)):self.q.pop()self.q.append((a, b))def get(self, x): #xでの最小値while len(self.q)>=2 and self.f(self.q[0], x)>=self.f(self.q[1], x):self.q.popleft()return self.f(self.q[0], x)def dfs(l, r): # [l, r)global ansif l>=r:returnm = (l+r)//2# [l, m)cht = CHT()for i in range(m+1, r+1):cht.add_line(-2*i, i*i+acc[i])res = 10**18for i in range(l, m):res = min(res, cht.get(i)+i*i-acc[i])ans[i] = min(ans[i], res)# [m, r)cht = CHT()for i in range(l, m+1):cht.add_line(-2*i, i*i-acc[i])hoge = defaultdict(lambda: 10**18)for i in range(m+1, r+1):hoge[i] = cht.get(i)+i*i+acc[i]for i in range(r, m, -1):hoge[i] = min(hoge[i], hoge[i+1])ans[i-1] = min(ans[i-1], hoge[i])dfs(l, m)dfs(m+1, r)N = int(input())A = list(map(int, input().split()))acc = [0]for Ai in A:acc.append(acc[-1]+Ai)ans = [10**18]*Ndfs(0, N)for i in range(N):print(ans[i])