結果
問題 | No.913 木の燃やし方 |
ユーザー |
![]() |
提出日時 | 2024-04-17 15:54:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 911 ms / 3,000 ms |
コード長 | 2,047 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 136,900 KB |
最終ジャッジ日時 | 2024-10-09 09:58:18 |
合計ジャッジ時間 | 28,035 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
from collections import dequeclass Convex_Hull_Trick_deque:"""f_i = a_ix + b_i とする。f_i の追加および、min_i f(x) の取得ができるデータ構造。ただし、傾き a_i は降順に追加されなければならない。また、クエリ x も昇順に実行されなければならない。"""def __init__(self):self.lines=deque()def add_line(self,a,b):lines=self.lineswhile len(lines) >= 2:a1,b1=lines[-2]a2,b2=lines[-1]if (a2-a1)*(b-b2)<(b2-b1)*(a-a2):breaklines.pop()lines.append((a, b))def __call__(self, x):lines=self.linesa,b=lines[0]y=a*x+bwhile len(lines) >= 2:a2, b2 = lines[1]y2 = a2 * x + b2if y < y2:breaky = y2lines.popleft()return yN=int(input())A=list(map(int,input().split()))C=[0]+Afor i in range(1,N+1):C[i]+=C[i-1]inf=1<<60ans_lst=[inf]*Ndef solve(l,r):if r-l==1:ans_lst[l]=min(ans_lst[l],1+A[l])elif r-l==2:ans_lst[l]=min(ans_lst[l],1+A[l],4+A[l]+A[l+1])ans_lst[l+1]=min(ans_lst[l+1],1+A[l+1],4+A[l]+A[l+1])else:m=(l+r)//2mi=[inf]*(r-l)CHT_left=Convex_Hull_Trick_deque()for i in range(l,m):CHT_left.add_line(-2*i,i*i-C[i])for j in range(m+1,r+1):mi[j-1-l]=min(mi[j-1-l],CHT_left(j)+j*j+C[j])CHT_right=Convex_Hull_Trick_deque()for j in range(m+1,r+1):CHT_right.add_line(-2*j,j*j+C[j])for i in range(l,m):mi[i-l]=min(mi[i-l],CHT_right(i)+i*i-C[i])for i in range(l+1,m):mi[i-l]=min(mi[i-l],mi[i-l-1])for j in range(r-2,m-1,-1):mi[j-l]=min(mi[j-l],mi[j-l+1])for i in range(l,r):ans_lst[i]=min(ans_lst[i],mi[i-l])solve(l,m)solve(m,r)solve(0,N)print(*ans_lst,sep="\n")