링고는 싱가포르 카니발에 놀러 갔다. 링고의 가방에는 상품을 받을 수 있는 티켓들이 있어서 게임에 사용하려고 한다. 각 티켓은 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[0],a[1],…,a[n−1]로 기록한다. 순서는 상관이 없다.
- 마스터는 뽑기 상자에서 특별한 카드 한 장을 꺼낸다. 그 카드에 인쇄된 정수를 b라고 하자.
- 마스터는 0부터 n−1까지의 각 i에 대해 a[i]와 b의 차이의 절대값을 계산한다. 차이의 절대값을 모두 더한 값을 S라고 하자.
- 이번 라운드에서 링고가 받게 되는 상품의 가격은 S이다.
- 이번 라운드에서 사용된 티켓들은 모두 버려지고 더 이상 사용될 수 없다.
모든 k번의 라운드가 끝난 후 남은 티켓들도 모두 버려진다.
그런데 자세히 보니 뽑기 상자에서 어떤 값이 인쇄된 카드가 랜덤한 것이 아니라는 것을 알게 되었다! 뽑기 상자 안에는 프린터가 있고 마스터가 정하는 값을 프린트할 수 있는 것이다. 각 라운드에서 마스터는 상품의 가격 S가 최소화되는 정수 b가 인쇄되도록 한다는 것을 알 수 있었다.
이러한 정보를 알게 된 링고는 라운드들에서 선택하는 티켓들을 최적화하고 싶어졌다. 즉, 링고는 모든 라운드에서 받는 상품 가치의 총합을 최대화하려고 한다.
구현 세부사항
다음 함수를 작성해야 한다.
int64 find_maximum(int k, int[][] x)
- k: 라운드 개수.
- x: 크기 n×m인 배열이다. 각 티켓에 인쇄된 정수를 저장하고 있다. 한 가지 색의 티켓들에 인쇄된 수들은 감소하지 않는 순서로 배열에 저장되어 있다.
- 이 함수는 정확히 한 번 호출된다.
- 이 함수는 아래에 정의된
allocate_tickets 함수를 정확히 한 번 호출해야 한다. 이 호출의 인자로 k번의 라운드에서 선택되는 티켓들을 저장하여 호출해야 한다. 티켓의 선택은 상품 가치의 총합을 최대화하여야 한다.
- 이 함수는 상품 가치의 최대 총합을 리턴하여야 한다.
함수 allocate_tickets는 다음과 같이 정의된다.
void allocate_tickets(int[][] s)
- s: 크기 n×m인 배열이다. 색 i인 티켓들 중 j번인 티켓이 라운드 r에 사용된 경우 s[i][j]=r이어야 한다. 해당 티켓이 사용되지 않는다면 값이 −1이어야 한다.
- 각 0≤i≤n−1에 대해서 s[i][0],s[i][1],…,s[i][m−1] 중에 0,1,2,…,k−1은 정확히 한 번씩 등장해야 하고 나머지 값들은 −1이어야 한다.
- 최적이 되도록 티켓을 고르는 방법이 여러 가지 있는 경우 그들 중 어떤 것을 기록해도 좋다.
예제
예제 1
다음 호출을 보자.
find_maximum(2, [[0, 2, 5],[1, 1, 3]])
호출의 의미는 다음과 같다.
- 라운드의 수는 k=2이다.
- 0번 색의 티켓에 인쇄된 수들은 각각 0, 2, 5이다.
- 1번 색의 티켓에 인쇄된 수들은 각각 1, 1, 3이다.
상품 가치의 총합을 최대화하는 선택 방법 중 한 가지는 아래와 같다.
- 라운드 0에서, 링고는 0번 색 티켓 중 0번(인쇄된 수는 0)과 1번 색 티켓 중 2번(인쇄된 수는 3)을 고른다. 이 라운드에서 최소 상품 가치는 3이다. 예를 들어, 마스터가 b=1을 고르면 상품 가치는 ∣1−0∣+∣1−3∣=1+2=3이 된다.
- 라운드 1에서, 링고는 0번 색 티켓 중 2번(인쇄된 수는 5)과 1번 색 티켓 중 1번(인쇄된 수는 1)을 고른다. 이 라운드에서 최소 상품 가치는 4이다. 예를 들어, 마스터가 b=3을 고르면 상품 가치는 ∣3−1∣+∣3−5∣=2+2=4이다.
- 따라서 전체 상품 가치는 3+4=7이다.
위와 같이 선택한 경우 아래와 같이 인자를 설정하여 allocate_tickets를 호출해야 한다.
allocate_tickets([[0, -1, 1], [-1, 1, 0]])
마지막으로 find_maximum은 7을 리턴해야 한다.
예제 2
다음 호출을 보자.
find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])
이 호출의 의미는 아래와 같다.
- 단 한 번의 라운드가 있다.
- 0번 색의 티켓에는 각각 5, 9가 인쇄되어 있다.
- 1번 색의 티켓에는 각각 1, 4가 인쇄되어 있다.
- 2번 색의 티켓에는 각각 3, 6이 인쇄되어 있다.
- 3번 색의 티켓에는 각각 2, 7이 인쇄되어 있다.
상품 가치의 총합을 최대화하는 선택 방법 중 한 가지는 아래와 같다.
- 라운드 0에서 링고는 0번 색의 티켓 중 1번(인쇄된 값은 9), 1번 색의 티켓 중 0번(인쇄된 값은 1), 2번 색의 티켓 중 0번(인쇄된 값은 3), 3번 색의 티켓 중 1번(인쇄된 값은 7)을 선택한다. 이 라운드에서 가능한 최소의 상품 가치는 12이다. 예를 들어 마스터가 b=3을 선택할 경우 가치는 ∣3−9∣+∣3−1∣+∣3−3∣+∣3−7∣=6+2+0+4=12이다.
위와 같이 선택한 경우 아래와 같이 인자를 설정하여 allocate_tickets를 호출해야 한다.
allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])
마지막으로 find_maximum은 12를 리턴해야 한다.
제약 조건
- 2≤n≤1500이고, n은 짝수이다.
- 1≤k≤m≤1500
- 모든 0≤i≤n−1, 0≤j≤m−1에 대해 0≤x[i][j]≤109
- 모든 0≤i≤n−1, 1≤j≤m−1에 대해 x[i][j−1]≤x[i][j]
서브태스크
- (11점) m=1
- (16점) k=1
- (14점) 모든 0≤i≤n−1, 0≤j≤m−1에 대해 0≤x[i][j]≤1
- (14점) k=m
- (12점) n,m≤80
- (23점) n,m≤300
- (10점) 추가적인 제한이 없다.