Problem:

デジットＫ

　

アイヅ赤べこ店では、デジットＫと呼ばれるユニークな「くじ」を販売しています。各くじには、左から右へ向かって1列に$N$個の数字が並んでいます。ただし、書かれているのは１から９までの数字です。

くじの購入者は、これらの数字から$K$個の数字を消去し、残った$N-K$個の数字を左から順番に並べてできる数をポイントとして獲得することができます。たとえば$K=3$のとき、くじに$1414213$と書かれていれば、左から$1$、$1$、$2$を選択して消去することで$4413$ポイントを獲得することができます。

  数字の列と整数$K$が与えられたとき、獲得できるポイントの最大値を出力するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $K$
$a_1$ $a_2$ ... $a_N$

  １行目に数字の数$N$ ($1 \leq N \leq 200,000$)と整数$K$ ($0 \leq K < N$)が与えられる。２行目にくじに書かれている$N$個の数$a_i$ ($1 \leq a_i \leq 9$)が与えられる。
								      

出力

ポイントの最大値を１行に出力する。

入出力例

入力例１

7 3
1 4 1 4 2 1 3

出力例１

4423

入力例２

4 1
1 1 9 9

出力例２

199



Sample input:
7 3
1 4 1 4 2 1 3


Sample output:
4423

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


class Info:
    def __init__(self,arg_num,arg_loc):
        self.num = arg_num
        self.loc = arg_loc

    def __lt__(self,another):
        if self.num != another.num:
            return self.num > another.num
        else:
            return self.loc < another.loc


N,K = map(int,input().split())

Q = []

rest = N
need_out = N-K
out = 0

table = list(map(int,input().split()))

for loc in range(N):
    tmp = table[loc]
    heappush(Q,Info(tmp,loc))
    rest -= 1

    if out+rest >= need_out:
        continue

    info = heappop(Q)
    print("%d"%(info.num),end="")

    while len(Q) > 0 and Q[0].loc <= info.loc:
        heappop(Q)

print("")