Ringo đang tham dự một lễ hội ở Singapore. Cậu có một số vé dự thưởng trong túi và muốn sử dụng chúng tại quầy trò chơi có thưởng. Mỗi vé thuộc một trong \(n\) màu và có in một số nguyên không âm. Các số nguyên in trên những vé khác nhau có thể bằng nhau. Theo một luật lệ kỳ quặc của lễ hội, \(n\) được bảo đảm là số chẵn.

Ringo có \(m\) vé mỗi màu trong túi, tổng cộng \(n\cdot m\) vé. Vé \(j\) của màu \(i\) có in số nguyên \(x[i][j]\) (\(0 \le i \le n-1\) và \(0 \le j \le m-1\)).

Trò chơi diễn ra trong \(k\) vòng, đánh số từ \(0\) đến \(k-1\). Mỗi vòng diễn ra theo thứ tự sau:

1. Ringo chọn từ túi một tập gồm \(n\) vé, mỗi màu đúng một vé, rồi đưa tập vé này cho người quản trò.
2. Người quản trò ghi lại các số nguyên \(a[0],a[1],\ldots,a[n-1]\) in trên các vé trong tập. Thứ tự của \(n\) số nguyên này không quan trọng.
3. Người quản trò rút một thẻ đặc biệt từ hộp bốc thăm may mắn và ghi lại số nguyên \(b\) in trên thẻ đó.
4. Người quản trò tính độ chênh lệch tuyệt đối giữa \(a[i]\) và \(b\) với mỗi \(i\) từ \(0\) đến \(n-1\). Gọi \(S\) là tổng các độ chênh lệch tuyệt đối này.
5. Trong vòng này, người quản trò trao cho Ringo phần thưởng có giá trị bằng \(S\).
6. Các vé trong tập bị bỏ đi và không thể sử dụng trong các vòng sau.

Các vé còn lại trong túi Ringo sau \(k\) vòng chơi cũng bị bỏ đi.

Quan sát kỹ, Ringo nhận ra trò chơi đã bị gian lận! Thực ra có một máy in bên trong hộp bốc thăm may mắn. Trong mỗi vòng, người quản trò tìm một số nguyên \(b\) làm cho giá trị phần thưởng của vòng đó nhỏ nhất. Giá trị được chọn được in lên thẻ đặc biệt của vòng đó.

Biết tất cả những thông tin này, Ringo muốn phân bổ vé cho các vòng chơi. Cụ thể, cậu muốn chọn tập vé sử dụng trong mỗi vòng để tổng giá trị các phần thưởng là lớn nhất.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau:

long long find_maximum(int k, std::vector<std::vector<int>> x);

• \(k\): số vòng chơi.
• \(x\): mảng kích thước \(n\times m\) mô tả số nguyên in trên từng vé. Các vé của mỗi màu được sắp xếp theo thứ tự không giảm của số nguyên in trên vé.
• Hàm này được gọi đúng một lần.
• Hàm phải gọi allocate_tickets (mô tả bên dưới) đúng một lần, mô tả \(k\) tập vé, mỗi tập cho một vòng. Cách phân bổ phải làm tổng giá trị các phần thưởng lớn nhất.
• Hàm phải trả về tổng giá trị phần thưởng lớn nhất.

Hàm allocate_tickets được định nghĩa như sau:

void allocate_tickets(std::vector<std::vector<int>> s);

• \(s\): mảng kích thước \(n\times m\). Giá trị \(s[i][j]\) phải bằng \(r\) nếu vé \(j\) của màu \(i\) được sử dụng trong tập vé của vòng \(r\), hoặc bằng \(-1\) nếu vé đó không được sử dụng.
• Với mỗi \(0 \le i \le n-1\), trong các phần tử \(s[i][0],s[i][1],\ldots,s[i][m-1]\), mỗi giá trị \(0,1,2,\ldots,k-1\) phải xuất hiện đúng một lần; tất cả các phần tử còn lại phải bằng \(-1\).
• Nếu có nhiều cách phân bổ đạt tổng giá trị phần thưởng lớn nhất, bạn có thể báo cáo bất kỳ cách nào.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n m k.
• Dòng \(2+i\) (\(0 \le i \le n-1\)): x[i][0] x[i][1] ... x[i][m-1].

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1\): giá trị trả về của find_maximum.
• Dòng \(2+i\) (\(0 \le i \le n-1\)): s[i][0] s[i][1] ... s[i][m-1].

Ràng buộc

• \(2 \le n \le 1500\), trong đó \(n\) là số chẵn.
• \(1 \le k \le m \le 1500\).
• \(0 \le x[i][j] \le 10^9\) (\(0 \le i \le n-1\), \(0 \le j \le m-1\)).
• \(x[i][j-1] \le x[i][j]\) (\(0 \le i \le n-1\), \(1 \le j \le m-1\)).

Phân nhóm

Ví dụ

find_maximum(2, [[0, 2, 5], [1, 1, 3]])

    - Ở vòng $1$, Ringo chọn vé $2$ của màu $0$ (in số $5$) và vé $1$ của màu $1$ (in số $1$). Giá trị phần thưởng nhỏ nhất có thể trong vòng này là $4$. Ví dụ, người quản trò có thể chọn $b=3$:

    - Vì vậy, tổng giá trị phần thưởng là:

    Để báo cáo cách phân bổ này, hàm `find_maximum` phải thực hiện lời gọi `allocate_tickets` sau:

    ```text
    allocate_tickets([[0, -1, 1], [-1, 1, 0]])
    ```

    Cuối cùng, hàm `find_maximum` phải trả về $7$.

find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])

    Để báo cáo phương án này, hàm `find_maximum` phải thực hiện lời gọi `allocate_tickets` sau:

    ```text
    allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])
    ```

    Cuối cùng, hàm `find_maximum` phải trả về $12$.

Nguồn

IOI 2020, Ngày 1 — Carnival Tickets (tickets). Đề chính thức tiếng Anh và bản dịch tiếng Việt.