#879. ABREC

Bộ nhớ: 256 MiB Thời gian: 2000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho bảng chữ kích thước 𝑚×𝑛 , mỗi ô chứa một ký tự A hoặc B. Một hình chữ nhật con của bảng được gọi là bảng ABREC bậc 𝑘 nếu số lượng ký tự A và số lượng ký tự B trong bảng con chênh lệch không quá 𝑘 .

Yêu cầu: Cho bảng chữ kích thước 𝑚×𝑛 và số nguyên 𝑘 , hãy tìm bảng con là bảng ABREC lớn nhất.

Dữ liệu vào:

  • Dòng đầu chứa số nguyên 𝑇 là số bộ dữ liệu;
  • 𝑇 nhóm dòng sau, mỗi dòng mô tả một bộ dữ liệu có dạng:
    • Dòng đầu chứa ba số nguyên 𝑚, 𝑛, 𝑘 ;
    • 𝑚 dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài 𝑛 chỉ gồm ký tự A hoặc B.

Dữ liệu ra:

  • Gồm một số dòng, mỗi dòng chứa một số là số lượng ô trong bảng tìm được tương ứng với dữ liệu vào.

Ví dụ:

Dữ liệu vào:

2
3 4 0
AAAA
BBBB
BAAA
3 4 1
AAAA
BBBB
BAAA

Dữ liệu ra:

8
9

Giới hạn:

  • Subtask \#1: 𝑚 × 𝑛 ≤ 100 ;
  • Subtask \#2: 𝑚 × 𝑛 ≤ 2000 ;
  • Subtask \#3: 𝑚 × 𝑛 ≤ 40000; 𝑘 = 0 ;
  • Subtask \#4: 𝑚 × 𝑛 ≤ 60000 .