PreVOI Phú Thọ 2023 - Ngày 14/02

Tỉ phú Vương dự định sẽ xây một thủy cung thu hút khách du lịch. Để thực hiện dự định đó, ông ta đã mua \(n\) chú cá và \(m\) bể thủy sinh. Chú cá thứ \(i\) có sức mạnh là \(a_i\).

Vương cần phải quyết định xem, với mỗi chú cá thì ông sẽ đặt vào bể thủy sinh nào. Tuy nhiên, việc này không hề đơn giản, khi ông sẽ phải xem xét đến giới hạn không gian và khả năng kìm hãm sự phát triển lẫn nhau giữa những chú cá trong cùng một bể. Sau những tính toán kĩ lưỡng, ông đã ước tính rằng mức độ bất ổn của mỗi chú cá sẽ bằng tổng sức mạnh của các chú cá nằm cùng bể thủy sinh với chú cá đó (bao gồm cả bản thân chú cá đó).

Yêu cầu: Hãy giúp tỉ phú Vương đặt các chú cá vào các bể thủy sinh sao cho tổng độ bất ổn của các chú cá là nhỏ nhất.

Input

• Dữ liệu vào từ file văn bản AQUARIUM.INP:
  • Dòng đầu tiên gồm hai số nguyên \(n\) và \(m\) (\(1 \le m \le n \le 2000\)) cho biết số chú cá và số bể thủy sinh.
  • Dòng thứ hai gồm \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) cho biết sức mạnh của các chú cá.
• Hai số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra file văn bản AQUARIUM.OUT một số nguyên duy nhất là tổng độ bất ổn nhỏ nhất của các chú cá.

Example

6 3
9 2 11 3 5 8

75

4 4
10 20 30 40

100

Hạn chế

• Có \(20\%\) số test ứng với \(n \le 8\).
• Có \(20\%\) số test khác ứng với \(n \le 15\).
• Có \(20\%\) số test khác ứng với \(m = 2\).
• Có \(30\%\) số test khác ứng với \(n \le 100\).
• \(10\%\) số test còn lại không có giới hạn gì thêm.

Khi luyện tập sang dạng bài xử lý xâu cho kì thi học sinh giỏi quốc gia sắp tới, Tuấn gặp một bài toán thú vị như sau:

Cho một xâu \(S = S_1 S_2 \dots S_n\) gồm \(n\) kí tự latin viết thường và một số nguyên không âm \(d\), các kí tự của \(S\) được đánh số từ \(1\) đến \(n\) từ trái qua phải.

Tiếp theo cho một số nguyên \(k\) (\(1 \le k \le n\)) và tạo ra \(m = \lfloor \frac{n}{k} \rfloor\) xâu độ dài \(k\), xâu thứ \(i\) trong \(m\) xâu là một xâu các kí tự con liên tiếp độ dài \(k\) của \(S\) bắt đầu từ vị trí \((i - 1) \cdot k + 1\). Nhắc lại, \(\lfloor z \rfloor\) là phép toán lấy phần nguyên của số \(z\). Nói một cách khác thì xâu \(S\) được cắt thành \(m\) xâu độ dài \(k\) và bỏ đi phần thừa. Kí hiệu xâu thứ \(i\) trong \(m\) xâu vừa được cắt là \(P_i\), khi đó \(P_i = S_{(i-1)\cdot k+1} S_{(i-1)\cdot k+2} \dots S_{i\cdot k}\).

Định nghĩa \(\text{dist}(X, Y)\) là khoảng cách Hamming của hai xâu \(X\) và \(Y\) có cùng độ dài \(k\), nghĩa là số vị trí \(u\) (\(1 \le u \le k\)) mà kí tự thứ \(u\) của \(X\) khác kí tự thứ \(u\) của \(Y\). Gọi \(f(k) = |\{(i, j) \mid (1 \le i < j \le m) \text{ thoả mãn } \text{dist}(P_i, P_j) \le d\}|\). Nói một cách khác, \(f(k)\) là số cặp xâu trong các xâu \(P\) thỏa mãn hai xâu đó khác nhau ở nhiều nhất \(d\) vị trí.

Yêu cầu: Với mỗi giá trị \(k\) từ \(1\) đến \(n\), hãy tính giá trị \(f(k)\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) (\(1 \le n \le 5 \times 10^4\)) và \(d\) (\(0 \le d \le 1\)).
• Dòng thứ hai chứa xâu \(s\) độ dài \(n\), gồm \(n\) kí tự latin viết thường.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra \(n\) số nguyên trên một dòng, số nguyên thứ \(k\) là giá trị của \(f(k)\). Các số trên cùng một dòng cách nhau bởi dấu cách.

Example

11 0
ababaaabaaa

31 4 1 0 0 0 0 0 0 0 0

11 1
ababaaabaaa

55 10 1 1 0 0 0 0 0 0 0

Scoring

• Có \(25\%\) test ứng với \(d \le 1, N \le 1000\).
• Có \(25\%\) test khác ứng với \(d \le 1, N \le 3000\).
• Có \(25\%\) test khác ứng với \(d = 0, N \le 50000\).
• \(25\%\) còn lại test ứng với \(d \le 1, N \le 50000\).

Cô Thái rất thích sự tròn trĩnh của những chữ số \(0\). Là giáo viên chuyên tin, cô Thái cho các bạn học sinh giỏi làm bài tập đếm số lượng hình chữ nhật chỉ chứa toàn số \(0\) trong một bảng hình chữ nhật. Cụ thể, cho một bảng hình chữ nhật kích thước \(n \times n\) ô, mỗi ô chỉ chứa số \(0\) hoặc \(1\). Các hàng đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột đánh số từ \(1\) đến \(n\) từ trái qua phải. Có \(q\) truy vấn, mỗi truy vấn sẽ thay đổi giá trị của một ô từ \(0\) thành \(1\) hoặc từ \(1\) thành \(0\).

Yêu cầu: Với mỗi truy vấn, sau khi thay đổi giá trị hãy đếm số hình chữ nhật con (tính cả hình chữ nhật ban đầu) có cạnh song song với cạnh của bảng mà chỉ chứa các số \(0\).

Input

• Dòng đầu chứa hai số nguyên \(n, q\) (\(1 \le n, q \le 5000\)).
• Dòng thứ \(i\) trong số \(n\) dòng tiếp theo chứa một xâu \(01\) độ dài \(n\) mô tả hàng thứ \(i\) của bảng ban đầu.
• Dòng thứ \(i\) trong số \(q\) dòng tiếp theo chứa hai số nguyên \(r, c\) (\(1 \le r, c \le n\)) mô tả tọa độ ô thay đổi giá trị trong truy vấn thứ \(i\).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra gồm \(q + 1\) dòng trong đó:
  • Dòng đầu là số lượng hình chữ nhật con thỏa mãn của bảng ban đầu;
  • Mỗi dòng trong số \(q\) dòng tiếp theo ghi một số nguyên là kết quả của truy vấn tương ứng.

Example

4 3
0001
0100
1000
0010
2 3
2 2
3 1

29
23
31
45

Hạn chế

• Có \(20\%\) số test ứng với \(n, q \le 50\).
• Có \(20\%\) số test khác ứng với \(n, q \le 150\).
• Có \(20\%\) số test khác ứng với \(n, q \le 400\).
• Có \(20\%\) số test khác ứng với \(n, q \le 1000\).
• \(20\%\) số test còn lại không có giới hạn gì thêm.