結果

問題 No.798 コレクション
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-06-30 16:35:11
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 3,890 bytes
コンパイル時間 156 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 557,652 KB
最終ジャッジ日時 2024-06-27 02:46:40
合計ジャッジ時間 4,536 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 10 MLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

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

"""
bi
k(k+k//2>=nk)
kk
使
s->gk
b[i]
idi
jsj
di->g01
sj->dia[j]+i*b[j]1
"""
def main0(n,ab):
k=0
cnt=0
for i in range(n):
cnt+=1
if i%2==1:
cnt+=1
if cnt>=n:
k=i+1
break
# k
todo=[[i] for i in range(n)]
allpat=[]
while todo:
v=todo.pop()
if len(v)==k:
allpat.append(v)
continue
for nv in range(max(v)+1,n):
todo.append(v+[nv])
ans=10**10
for pat in allpat:
ary=[]
for i in pat:
ary.append(ab[i][:])
ary.sort(key=lambda x:x[1],reverse=True)
tmp=sum([ary[i][0]+i*ary[i][1] for i in range(k)])
ans=min(ans,tmp)
return ans
#
from heapq import heappush, heappop
class MinCostFlow:
INF = 10**18
def __init__(self, N):
self.N = N
self.G = [[] for i in range(N)]
def add_edge(self, fr, to, cap, cost):
forward = [to, cap, cost, None]
backward = forward[3] = [fr, 0, -cost, forward]
self.G[fr].append(forward)
self.G[to].append(backward)
def flow(self, s, t, f):
N = self.N; G = self.G
INF = MinCostFlow.INF
res = 0
H = [0]*N
prv_v = [0]*N
prv_e = [None]*N
d0 = [INF]*N
dist = [INF]*N
while f:
dist[:] = d0
dist[s] = 0
que = [(0, s)]
while que:
c, v = heappop(que)
if dist[v] < c:
continue
r0 = dist[v] + H[v]
for e in G[v]:
w, cap, cost, _ = e
if cap > 0 and r0 + cost - H[w] < dist[w]:
dist[w] = r = r0 + cost - H[w]
prv_v[w] = v; prv_e[w] = e
heappush(que, (r, w))
if dist[t] == INF:
return None
for i in range(N):
H[i] += dist[i]
d = f; v = t
while v != s:
d = min(d, prv_e[v][1])
v = prv_v[v]
f -= d
res += d * H[t]
v = t
while v != s:
e = prv_e[v]
e[1] -= d
e[3][1] += d
v = prv_v[v]
return res
def main1(n,ab):
k=0
cnt=0
for i in range(n):
cnt+=1
if i%2==1:
cnt+=1
if cnt>=n:
k=i+1
break
# k
mcf=MinCostFlow(n+n+2)
# i:i
# n+j:j
# n+n:start
# n+n+1:goal
for i,(a,b) in enumerate(ab):
mcf.add_edge(n+n,i,1,0)
for j in range(n):
mcf.add_edge(i,n+j,1,a+b*j)
for j in range(n):
mcf.add_edge(n+j,n+n+1,1,0)
ans=mcf.flow(n+n,n+n+1,k)
return ans
if __name__=='__main__':
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
ret1=main1(n,ab)
print(ret1)
#ret0=main0(n,ab)
#print(ret0)
from random import randint
if __name__=='__main__1':
for _ in range(100):
n=randint(5,10)
ab=[]
for _ in range(n):
a=randint(1,30)
b=randint(1,30)
ab.append([a,b])
ret1=main1(n,ab)
ret0=main0(n,ab)
if ret0!=ret1:
print(n)
for x in ab:print(*x)
print((ret0,ret1))
break
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0