結果
問題 | No.798 コレクション |
ユーザー |
|
提出日時 | 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 |
ソースコード
"""奇数の日のキャンペーンがない場合、biの大きい順に買うのが最適キャンペーンを考慮する。k日ですべて買えるとする。(k+k//2>=nとなる最小のk)k個の商品はお金を払うので、k個の商品を普通に買うときの最小値を求める。ある商品を買うとそれ以降その商品は買えない。ある日に商品を買うとその日はもう商品を買えない。日をまたぐとコストが変わる。操作をするとそれ以降の操作に制約ができる。最小費用流を使う。s->gまでkを流すのに必要最小のコストb[i]の考慮をどうするか。i日目を示す頂点di商品jを示す頂点sjdi->gにコスト0容量1の辺sj->diにコストa[j]+i*b[j]容量1の辺"""def main0(n,ab):k=0cnt=0for i in range(n):cnt+=1if i%2==1:cnt+=1if cnt>=n:k=i+1break# k個の商品を買うtodo=[[i] for i in range(n)]allpat=[]while todo:v=todo.pop()if len(v)==k:allpat.append(v)continuefor nv in range(max(v)+1,n):todo.append(v+[nv])ans=10**10for 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, heappopclass MinCostFlow:INF = 10**18def __init__(self, N):self.N = Nself.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.GINF = MinCostFlow.INFres = 0H = [0]*Nprv_v = [0]*Nprv_e = [None]*Nd0 = [INF]*Ndist = [INF]*Nwhile f:dist[:] = d0dist[s] = 0que = [(0, s)]while que:c, v = heappop(que)if dist[v] < c:continuer0 = dist[v] + H[v]for e in G[v]:w, cap, cost, _ = eif cap > 0 and r0 + cost - H[w] < dist[w]:dist[w] = r = r0 + cost - H[w]prv_v[w] = v; prv_e[w] = eheappush(que, (r, w))if dist[t] == INF:return Nonefor i in range(N):H[i] += dist[i]d = f; v = twhile v != s:d = min(d, prv_e[v][1])v = prv_v[v]f -= dres += d * H[t]v = twhile v != s:e = prv_e[v]e[1] -= de[3][1] += dv = prv_v[v]return resdef main1(n,ab):k=0cnt=0for i in range(n):cnt+=1if i%2==1:cnt+=1if cnt>=n:k=i+1break# k個の商品を買うmcf=MinCostFlow(n+n+2)# i:商品i# n+j:j日目# n+n:start# n+n+1:goalfor 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 ansif __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 randintif __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