結果

問題 No.1251 絶対に間違ってはいけない最小化問題
ユーザー 👑 Kazun
提出日時 2021-09-20 20:09:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 481 ms / 2,000 ms
コード長 3,834 bytes
コンパイル時間 190 ms
コンパイル使用メモリ 81,664 KB
実行使用メモリ 155,380 KB
最終ジャッジ日時 2024-07-02 18:48:25
合計ジャッジ時間 23,513 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

class Binary_Indexed_Tree():
def __init__(self, L, calc, unit, inv, index=1):
""" calc N Binary Indexed Tree
calc: (2, )
unit: calc (x+e=e+x=xe)
inv : calc (1, x+y(x)=y(x)+x=e y(x))
"""
self.calc=calc
self.unit=unit
self.inv=inv
self.index=index
N=len(L)
d=max(1,(N-1).bit_length())
k=2**d
X=[None]+[unit]*k
self.num=k
self.depth=d
if L:
for i in range(len(L)):
p=i+1
while p<=k:
X[p]=self.calc(X[p],L[i])
p+=p&(-p)
self.data=X
def index_number(self, k, index=1):
""" k .
k :
index:
"""
return self.sum(k,k,index)
def add(self, k, x, index=1):
""" k x , .
k :
x :
index:
right:
"""
p=k+(1-index)
while p<=self.num:
self.data[p]=self.calc(self.data[p],x)
p+=p&(-p)
def update(self, k, x, index=1):
""" k x , .
k:
x:
"""
a=self.index_number(k,index)
y=self.calc(self.inv(a),x)
self.add(k,y,index)
def sum(self, From, To, index=1):
""" From To .
※From!=1使, .
From :
To :
index:
"""
alpha=max(1,From+(1-index))
beta=min(self.num,To+(1-index))
if alpha==1:
return self.__section(beta)
else:
return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta))
def __section(self,x):
""" B[1]+...+B[x] . """
S=self.unit
while x>0:
S=self.calc(self.data[x],S)
x-=x&(-x)
return S
def all_sum(self):
return self.data[-1]
def binary_search(self, cond, index=1):
""" cond(B[1]+...+B[k]) k .
cond: 調
※ cond(uint)=True index-1
※ cond(B[1]+...+B[k]) k self.num+index
"""
if cond(self.unit):
return index-1
j=0
r=self.num
t=r
data=self.data
alpha=self.unit
for _ in range(self.depth+1):
if j+t<=self.num:
beta=self.calc(alpha,data[j+t])
if not cond(beta):
alpha=beta
j+=t
t>>=1
return j+index
def __getitem__(self,index):
if isinstance(index,int):
return self.index_number(index,self.index)
else:
return [self.index_number(t,self.index) for t in index]
def __setitem__(self,index,val):
self.update(index,val,self.index)
#==================================================
from operator import add,neg
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A_sort=sorted(A)
A_ind={a:i for i,a in enumerate(A_sort)}
T=Binary_Indexed_Tree([0]*N,add,0,neg,0)
for a,b in zip(A,B):
T.add(A_ind[a],b,0)
B_sum=sum(B)
X=A_sort[T.binary_search(lambda x:x>=(B_sum+1)//2,0)]
Y=0
for a,b in zip(A,B):
Y+=b*abs(X-a)
print(X,Y)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0