Carnival Tickets timer 2초 memory 1024MB

링고는 싱가폴 카니발에 놀러 갔다.

링고의 가방에는 상품을 받을 수 있는 티켓들이 있어서 게임에 사용하려고 한다.

각 티켓은 n가지 중 한 색이고 음이 아닌 정수가 하나 인쇄되어 있다.

서로 다른 티켓들에 인쇄된 수가 같은 경우도 있다.

게임 규칙의 특정한 사유 때문에 n은 항상 짝수이다.

링고의 가방에 n가지 색 각각에 대해 티켓이 정확히 m개가 있다.

즉, 모두 n × m개의 티켓이 있다. 색이 i번인 티켓들 중 j번인 티켓에는 정수 x_i, j가 인쇄되어 있다. (0 ≤ i ≤ n - 1, 0 ≤ j ≤ m - 1)

게임은 k번의 라운드로 진행된다.

라운드들은 0부터 k - 1까지 번호가 붙어 있다.

각 라운드는 다음과 같은 과정으로 진행된다.

- 링고는 가방의 티켓들 중 각 색에서 하나씩 뽑아서 n개의 티켓을 모은다. 모은 티켓을 마스터에게 전달한다.

- 마스터는 각 티켓에 인쇄된 정수들을 a₀, a₁, ... , a_n-1로 기록한다. 순서는 상관이 없다.

- 마스터는 뽑기 상자에서 특별한 카드 한 장을 꺼낸다. 그 카드에 인쇄된 정수를 b라고 하자.

- 마스터는 각 a_i와 b의 차이의 절대값을 모두 (0 ≤ i ≤ n - 1) 계산한다. 차이의 절대값을 모두 더한 값을 S라고 하자.

- 이번 라운드에서 링고가 받게 되는 상품의 가격은 S이다.

- 이번 라운드에서 사용된 티켓들은 모두 버려지고 더 이상 사용될 수 없다.

모든 (k번의) 라운드가 끝난 후 남은 티켓들도 모두 버려진다.

그런데, 자세히 보니 뽑기 상자에서 어떤 값이 인쇄된 카드가 랜덤한 것이 아니라는 것을 알게 되었다!

뽑기 상자 안에는 프린터가 있고 마스터가 정하는 값을 프린트할 수 있는 것이다.

각 라운드에서 마스터는 상품의 가격 S가 최소화되는 정수 b가 인쇄되도록 한다는 것을 알수 있었다.

이러한 정보를 알게 된 링고는 라운드들에서 선택하는 카드들을 최적화하고 싶어졌다.

즉, 링고는 모든 라운드에서 받는 상품 가치의 총합을 최대화하려고 한다.