Problem:


あみだくじ  

問題

  あなたは J 君と一緒にあみだくじを使って遊んでいる.あみだくじは n 本の縦棒と
m 本の横棒からなる.縦棒には左から順に 1 から n の番号がついており,縦棒 i の下端には正整数 si が書かれている.

図 3-1 あみだくじの例(n = 4, m = 5, s1 = 20, s2 = 80, s3 = 100, s4 = 50)

 縦棒 i の一番上から順に道をたどっていき到達した下端に書かれている整数が, 縦
棒 i を選んだ場合の得点である.例えば,図 3-1 では,縦棒 1 を選ぶと得点は 80 点
であり,縦棒 2 を選ぶと得点は 100 点である.

図 3-2 道のたどり方の例

 J 君は縦棒 1 から縦棒 k までの連続した k 本を選ぶことにした.それら k 本の縦棒を選んだときの点数の合計が J 君の得点となる.ただし,あなたはあみだくじ内の
横棒を一本選び,その横棒をあみだくじから削除することができる. (削除しなくてもよい.) もし,あなたが横棒を一本削除した場合は,削除後のあみだくじにおいて,
縦棒 1 から縦棒 k までの連続した k 本の縦棒を選んだときの点数の合計が J 君の得点となる.

 入力としてあみだくじの形と J 君の選ぶ縦棒の本数 k が与えられたとき,J 君の得
点の最小値を求めるプログラムを作成せよ.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

1 行目には 4 つの整数 n, m, h, k が空白区切りで書かれている. n (2 ≤ n ≤ 1000) は縦棒の本数を, m (1 ≤ m ≤ 100000) は横棒の本数を, h (2 ≤ h ≤ 1000) は縦棒の長さを,k (1 ≤ k ≤ n) は J 君が選ぶ縦棒の本数を表す.

続く n 行には縦棒の下端に書かれている点数が書かれている. i + 1 行目 (1 ≤ i ≤ n)には正整数 si が書かれている. また, s1 + s2 + ... + sn ≤ 2000000000 = 2 &times; 109 を満たす.

続く m 行には横棒の位置が書かれている.横棒には 1 から m までの番号がついている.i + n + 1 行目 (1 ≤ i ≤ m) には, 横棒 i の位置を表す 2 つの整数 ai, bi (1 ≤ ai ≤  n - 1, 1 ≤ bi ≤ h - 1) が空白区切りで書かれており,横棒 i が縦棒 ai と縦棒 ai + 1 を結び, 横棒 i の上端からの距離が bi であることを表す. ただし,どの 2 つの横棒も端点を共有することはない.

採点用データのうち,配点の 20 % 分は横棒を削除しない場合に J 君の得点が最少となる.また,配点の 30 % 分は n ≤ 20, m ≤ 30, h ≤  10 を満たし,配点の 60 % 分は m ≤ 1000 を満たす.

入力の終わりは 4つのゼロを含む行で示される. データセットの数は 10 を超えない．

出力

データセットごとに, J 君の得点の最小値を1 行に出力する.

入出力例

入力例

4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1
2 2 5 1
10
20
1 1
1 3
0 0 0 0

出力例

100
10

1つ目の例 は図 3-1 に対応し,あなたが横棒 4 (縦棒 1 と縦棒 2 を上端から距離 5 の場所で結ぶ横棒)を削除したとき,J 君の得点は最小になる.例 2 では,あなたが横棒を削除しない場合に J 君の得点が最小になる. (図3-3 を見よ.)

図 3-3

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
4 5 7 2
20
80
100
50
1 1
2 6
2 3
1 5
3 1
2 2 5 1
10
20
1 1
1 3
0 0 0 0


Sample output:
100
10

Submission status: Wrong Answer

Solution code:
while True:
    n,m,h,k = map(int, input().split())
    if n == 0: break
    pts = []
    for _ in range(n):
        pts.append(int(input()))
    bars = []
    for _ in range(m):
        bars.append(list(map(int, input().split())))
    bars.sort(key=lambda x: x[1])

    nos = [i for i in range(n)]
    barspt = []

    for bar in bars:
        b = bar[0]-1
        barspt.append([nos[b],nos[b+1],0,0])
        nos[b],nos[b+1] = nos[b+1],nos[b]

    nos = [i for i in range(n)]
    for barid in range(m-1,-1,-1):
        b0 = bars[barid][0]-1
        b1 = bars[barid][0]
        barspt[barid][2] = pts[nos[b0]]
        barspt[barid][3] = pts[nos[b1]]
        pts[nos[b0]],pts[nos[b1]] = pts[nos[b0]],pts[nos[b1]]
        nos[b0],nos[b1] = nos[b1],nos[b0]

    atari = -1
    minsc = 2*10**9+1
    for i in range(n-k+1):
        sc = sum(pts[i:i+k])
        if sc < minsc:
            minsc = sc
            atari = i

    hosei = 0
    for bar in barspt:
        if i <= bar[0]-1 and bar[0]-1 < i+k and (bar[1]-1 < i or i+k <= bar[1]-1):
            sc = bar[2]-bar[3]
            if sc < hosei: hosei = sc
        if i <= bar[1]-1 and bar[1]-1 < i+k and (bar[0]-1 < i or i+k <= bar[0]-1):
            sc = bar[3]-bar[2]
            if sc < hosei: hosei = sc

    print(minsc+hosei)

Submission status: Wrong Answer

Solution code:
while True:
  n,m,h,k = map(int,input().split())
  if not n: break
  s_lst = [int(input()) for _ in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:-x[1])
  h_map = [[s_lst[i] for i in range(n)] for _ in range(h)]
  for bar in b_lst:
    ind, height = bar[0], bar[1] - 1
    temp = h_map[height][ind]
    h_map[height + 1][ind - 1] = temp
    temp = h_map[height][ind - 1]
    h_map[height + 1][ind] = temp
  dic = dict()
  for i in range(n):
    dic[h_map[0][i]] = i
  ans = sum(h_map[0][:k])
  max_decrease = 0
  for bar in b_lst:
    ind, height = bar[0], bar[1] - 1
    v1 = h_map[height][ind]
    v2 = h_map[height][ind - 1]
    if v1 < v2 and v2 - v1 > max_decrease and dic[v1] >= k and dic[v2] < k:
      max_decrease = v2 - v1
    elif v2 < v1 and v1 - v2 > max_decrease and dic[v2] >= k and dic[v1] < k:
      max_decrease = v1 - v2
  print(ans - max_decrease)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n, m, h, k = map(int, input().split())
    if not n:
        break
    points = [int(input()) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = [points] + [None] * m
    pattern = 1

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            swap[pattern] = swap[0][:]
            for s in swap[:pattern]:
                s[ba], s[ba + 1] = s[ba + 1], s[ba]
            pattern += 1

    print(min(sum(s[:k]) for s in swap))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
while True:
  n,m,h,k = map(int,input().split())
  if not n: break
  s_lst = [int(input()) for _ in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:-x[1])
  def amida(b_lst, s_lst, used, k):
    if not b_lst:
      return sum(s_lst[0:k])
    elif used:
      for bar in b_lst:
        a = bar[0]
        temp = s_lst[a]
        s_lst[a] = s_lst[a - 1]
        s_lst[a - 1] = temp
      return sum(s_lst[0:k])
    else:
      save_s_lst = [i for i in s_lst]
      a = b_lst[0][0]
      temp = s_lst[a]
      s_lst[a] = s_lst[a - 1]
      s_lst[a - 1] = temp
      return min(amida(b_lst[1:], s_lst, 0, k), amida(b_lst[1:], save_s_lst, 1, k))

  print(amida(b_lst, s_lst, 0, k))

Submission status: Accepted

Solution code:
while True:
    n, m, h, k = map(int, input().split())
    if not n:
        break
    points = [int(input()) for _ in range(n)]
    bars = [tuple(map(int, input().split())) for _ in range(m)]
    bars_h = [set() for _ in range(h)]
    for ba, bh in bars:
        bars_h[bh].add(ba - 1)
    swap = list(range(n))
    history = set()

    for i in range(h - 1, 0, -1):
        for ba in bars_h[i]:
            l, r = swap[ba:ba + 2]
            history.add((l, r) if l < r else (r, l))
            swap[ba:ba + 2] = r, l
    swap_dict = {v: i for i, v in enumerate(swap)}
    min_score_d = 0
    for l, r in history:
        li, ri = swap_dict[l], swap_dict[r]
        if li > ri:
            l, r, li, ri = r, l, ri, li
        if li < k and k <= ri:
            min_score_d = min(min_score_d, points[r] - points[l])

    print(sum(points[x] for x in swap[:k]) + min_score_d)

Submission status: Accepted

Solution code:
while True:
    n,m,h,k = map(int, input().split())
    if n == 0: break
    pts = []
    for _ in range(n):
        pts.append(int(input()))
    bars = []
    for _ in range(m):
        bars.append(list(map(int, input().split())))
    bars.sort(key=lambda x: x[1])

    nos = [i for i in range(n)]
    barspt = []

    for bar in bars:
        b = bar[0]-1
        barspt.append([nos[b],nos[b+1],0,0])
        nos[b],nos[b+1] = nos[b+1],nos[b]

    nos = [i for i in range(n)]
    for barid in range(m-1,-1,-1):
        b0 = bars[barid][0]-1
        b1 = bars[barid][0]
        barspt[barid][2] = pts[nos[b0]]
        barspt[barid][3] = pts[nos[b1]]
        pts[nos[b0]],pts[nos[b1]] = pts[nos[b1]],pts[nos[b0]]

    atari = -1
    minsc = sum(pts[0:k])

    hosei = 0
    for bar in barspt:
        if atari <= bar[0]-1 and bar[0]-1 < atari+k and (bar[1]-1 < atari or atari+k <= bar[1]-1):
            sc = bar[2]-bar[3]
            if sc < hosei: hosei = sc
        if atari <= bar[1]-1 and bar[1]-1 < atari+k and (bar[0]-1 < atari or atari+k <= bar[0]-1):
            sc = bar[3]-bar[2]
            if sc < hosei: hosei = sc
    print(minsc+hosei)

Submission status: Accepted

Solution code:
while True:
  n,m,h,k = map(int,input().split())
  if not n: break
  s_lst = [int(input()) for _ in range(n)]
  i_lst = [i for i in range(n)]
  b_lst = [tuple(map(int,input().split())) for _ in range(m)]
  b_lst = sorted(b_lst,key=lambda x:x[1])
  pare_lst = []
  for bar in b_lst:
    ind = bar[0]
    temp = i_lst[ind]
    i_lst[ind] = i_lst[ind - 1]
    i_lst[ind - 1] = temp
    pare_lst.append((i_lst[ind], i_lst[ind - 1]))
#  print(i_lst)
  new_s_lst = [0] * n
  for i in range(n):
    new_s_lst[i_lst[i]] = s_lst[i]
#  print(s_lst)
  ans = sum(new_s_lst[:k])
#  print(ans)
#  print(pare_lst)
  max_dec = 0
  for pare in pare_lst:
    a = pare[0]
    b = pare[1]
#    print(a,b,s_lst[a],s_lst[b])
    if a < k and b >= k and new_s_lst[a] - new_s_lst[b] > max_dec:
      max_dec = new_s_lst[a] - new_s_lst[b]
    if b < k and a >= k and new_s_lst[b] - new_s_lst[a] > max_dec:
      max_dec = new_s_lst[b] - new_s_lst[a]
  print(ans - max_dec)

Submission status: Accepted

Solution code:
while(1):
    [n, m, h, k ] = [int(x) for x in input().split()]
    if n==0:
        break
    A=[]
    B=[ [] for x in range(h)]
    C=list(range(n))
    S=[0 for i in range(n)]
    X=[]
    for i in range(n):
        A.append(int(input()))
    for i in range(m):
        [a, b] = [int(x) for x in input().split()]
        B[b].append(a)
    for y in range(h):
        for a in B[y]:
            C[a-1:a+1]=[C[a], C[a-1]]
            X.append( sorted( C[a-1:a+1] ))
    for i in range(n):
        S[C[i]]=A[i]
    #print(S)
    ans=sum( S[:k ] )
    tmpdif=0
    for xx in X:
        if xx[0]<k and xx[1]>=k:
            tmpdif = min (tmpdif, S[xx[1]] - S[xx[0]] )
    print(ans + tmpdif)