結果
問題 | No.913 木の燃やし方 |
ユーザー | vwxyz |
提出日時 | 2024-04-17 15:54:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 928 ms / 3,000 ms |
コード長 | 2,047 bytes |
コンパイル時間 | 899 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 136,648 KB |
最終ジャッジ日時 | 2024-04-17 15:55:07 |
合計ジャッジ時間 | 29,124 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 48 ms
53,888 KB |
testcase_01 | AC | 45 ms
54,272 KB |
testcase_02 | AC | 44 ms
54,016 KB |
testcase_03 | AC | 154 ms
77,908 KB |
testcase_04 | AC | 162 ms
78,280 KB |
testcase_05 | AC | 166 ms
78,032 KB |
testcase_06 | AC | 158 ms
78,148 KB |
testcase_07 | AC | 132 ms
77,108 KB |
testcase_08 | AC | 775 ms
109,424 KB |
testcase_09 | AC | 745 ms
108,012 KB |
testcase_10 | AC | 780 ms
108,128 KB |
testcase_11 | AC | 729 ms
109,052 KB |
testcase_12 | AC | 807 ms
112,476 KB |
testcase_13 | AC | 718 ms
109,720 KB |
testcase_14 | AC | 738 ms
108,068 KB |
testcase_15 | AC | 704 ms
107,644 KB |
testcase_16 | AC | 805 ms
112,532 KB |
testcase_17 | AC | 752 ms
111,180 KB |
testcase_18 | AC | 729 ms
110,896 KB |
testcase_19 | AC | 562 ms
133,300 KB |
testcase_20 | AC | 773 ms
113,332 KB |
testcase_21 | AC | 880 ms
110,592 KB |
testcase_22 | AC | 879 ms
110,464 KB |
testcase_23 | AC | 842 ms
109,824 KB |
testcase_24 | AC | 828 ms
120,240 KB |
testcase_25 | AC | 536 ms
123,792 KB |
testcase_26 | AC | 742 ms
112,448 KB |
testcase_27 | AC | 533 ms
136,020 KB |
testcase_28 | AC | 814 ms
110,720 KB |
testcase_29 | AC | 798 ms
110,464 KB |
testcase_30 | AC | 823 ms
110,592 KB |
testcase_31 | AC | 633 ms
133,740 KB |
testcase_32 | AC | 664 ms
135,640 KB |
testcase_33 | AC | 643 ms
136,648 KB |
testcase_34 | AC | 879 ms
111,232 KB |
testcase_35 | AC | 928 ms
110,848 KB |
testcase_36 | AC | 881 ms
110,464 KB |
ソースコード
from collections import deque class 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.lines while len(lines) >= 2: a1,b1=lines[-2] a2,b2=lines[-1] if (a2-a1)*(b-b2)<(b2-b1)*(a-a2): break lines.pop() lines.append((a, b)) def __call__(self, x): lines=self.lines a,b=lines[0] y=a*x+b while len(lines) >= 2: a2, b2 = lines[1] y2 = a2 * x + b2 if y < y2: break y = y2 lines.popleft() return y N=int(input()) A=list(map(int,input().split())) C=[0]+A for i in range(1,N+1): C[i]+=C[i-1] inf=1<<60 ans_lst=[inf]*N def 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)//2 mi=[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")