結果

問題 No.1430 Coup de Coupon
コンテスト
ユーザー dot_haraai
提出日時 2021-05-09 21:01:02
言語 Nim
(2.2.0)
結果
MLE  
実行時間 -
コード長 2,758 bytes
コンパイル時間 5,129 ms
コンパイル使用メモリ 87,680 KB
実行使用メモリ 817,408 KB
最終ジャッジ日時 2024-09-19 01:50:40
合計ジャッジ時間 7,384 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6 MLE * 1 -- * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 18) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'times' [UnusedImport]
/home/judge/data/code/Main.nim(2, 37) Warning: imported and not used: 'deques' [UnusedImport]
/home/judge/data/code/Main.nim(2, 26) Warning: imported and not used: 'strformat' [UnusedImport]
/home/judge/data/code/Main.nim(2, 44) Warning: imported and not used: 'heapqueue' [UnusedImport]
/home/judge/data/code/Main.nim(2, 18) Warning: imported and not used: 'future' [UnusedImport]
/home/judge/data/code/Main.nim(1, 52) Warning: imported and not used: 'tables' [UnusedImport]
/home/judge/data/code/Main.nim(1, 60) Warning: imported and not used: 'sets' [UnusedImport]
/home/judge/data/code/Main.nim(1, 66) Warning: imported and not used: 'lists' [UnusedImport]
/home/judge/data/code/Main.nim(1, 73) Warning: imported and not used: 'intsets' [UnusedImport]
/home/judge/data/code/Main.nim(2, 8) Warning: imported and not used: 'critbits' [UnusedImport]

ソースコード

diff # 

import times, strutils, sequtils, math, algorithm, tables, sets, lists, intsets
import critbits, future, strformat, deques,heapqueue
template `max=`(x,y) = x = max(x,y)
template `min=`(x,y) = x = min(x,y)
template `mod=`(x,y) = x = x mod y
template scan2 = (scan(), scan())
template scan3 = (scan(), scan())
let read* = iterator: string {.closure.} =
    while true: (for s in stdin.readLine.split: yield s)
proc scan(): int = read().parseInt
proc scanf(): float = read().parseFloat
proc toInt(c:char): int =
  return int(c) - int('0')




type Edge = ref object
  frm:int
  to:int
  rev:int
  cap:int
  icap:int
  cost:int


var
  inf = int.high.div(4)


proc minCostFlow(G:var seq[seq[Edge]],src,term:int,initFlow:int):int=
  var
    nodeNum = G.len
    dist = newseqwith(nodeNum,0)
    prevv = newseqwith(nodeNum,0)
    preve = newseqwith(nodeNum,0)
    flow = initFlow
  while flow>0:
    dist.fill(inf)
    dist[src] = 0
    while true:
      var update = false
      for v in 0..<nodeNum:
        if dist[v] == inf:continue
        for i in 0..<G[v].len:
          var e = G[v][i]
          if e.cap > 0 and (dist[e.to] > dist[v]+e.cost):
            dist[e.to] = dist[v]+e.cost
            prevv[e.to] = v
            preve[e.to] = i
            update = true
      if not update:break
    if dist[term] == inf:return 0

    var
      d = flow
      v = term
    while v != src:
      d.min=G[prevv[v]][preve[v]].cap
      v = prevv[v]
    flow-=d
    result+=dist[term]*d
    v = term
    while v!=src:
      var
        e:Edge = G[prevv[v]][preve[v]]
        re:Edge = G[e.to][e.rev]
      e.cap-=d
      re.cap+=d
      v = prevv[v]


  return




proc solve():int=
  var 
    n = scan()
    c = scan()
    p = newseqwith(n,scan())
    nodeNum = n+c+2
    es = newseqwith(nodeNum,newseq[Edge]())
    #cap = newseqwith(n+c+2,newseq[int]())
    #cost = newseqwith(n+c+2,newseq[int]())
    #es = newseqwith(n+c+2,newseq[int]())
    src = 0
    term = n+c+1

  proc addEdge(s,t:int,cap:int,cost:int)=
    es[s].add(Edge(rev:es[t].len, frm:s,to:t,cap:cap,icap:cap,cost:cost))
    es[t].add(Edge(rev:es[s].len-1,frm:t,to:s,cap:0,icap:0,cost: -cost))

  
  for i in 1..c:
    addEdge(src,i,1,0)

  for i in 1..c:
    var
      (t,x)=(scan(),scan())
    for v in c+1..c+n:
      if t==1:
        addEdge(i,v,1,-min(p[v-(c+1)],x))
      else:
        addEdge(i,v,1,-(p[v-(c+1)]*x).div(100))
  
  for v in c+1..c+n:
    addEdge(v,term,1,0)
  
  result = p.sum()+minCostFlow(es,src,term,n)
  
  var gain = 0
  for i in 1..c:
    for e in es[i]:
      #echo fmt"{e.frm}, {e.to}, {e.cap}, {e.icap}, ({e.cost})"
      if e.icap==1 and e.cap==0:
        #echo fmt"Coupon {i} : Goods {e.to-c}"
        gain += e.cost
  return p.sum()+gain


  


    

echo solve()
0