Hội thi Tin học trẻ toàn quốc

BẢNG KÍ TỰ

Điểm: 100,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Pascal, Python

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

nguyenvietanh đã bình luận 2 ngày trước

giới hạn của k là bao nhiêu ?

1

anhkiet1306 đã bình luận 6 ngày trước

Sao bài này ko được làm bằng scratch

1

thienphat55CN đã bình luận 5 ngày trước

chắc của Bảng B

haonamdeptrai đã bình luận 10 ngày trước

include <iostream>

include <vector>

include <string>

include <algorithm>

include <climits>

using namespace std;

int getMaxBeautifulRect(const vector<string>& board, int m, int n, int k) { // Bảng giá trị: A -> +1, B -> -1 vector val(m, vector<int>(n)); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) val[i][j] = (board[i][j] == 'A') ? 1 : -1;

Copy

int maxArea = 0;

for (int top = 0; top < m; ++top) {
    vector<int> colSum(n, 0);
    for (int bottom = top; bottom < m; ++bottom) {
        for (int j = 0; j < n; ++j)
            colSum[j] += val[bottom][j];

        // Tìm đoạn con dài nhất có tổng chênh lệch <= k
        int left = 0, currSum = 0;
        vector<int> prefixSum(n + 1, 0);
        for (int i = 0; i < n; ++i)
            prefixSum[i + 1] = prefixSum[i] + colSum[i];

        for (int right = 0; right < n; ++right) {
            for (int left = 0; left <= right; ++left) {
                int diff = prefixSum[right + 1] - prefixSum[left];
                if (abs(diff) <= k) {
                    int width = right - left + 1;
                    int height = bottom - top + 1;
                    maxArea = max(maxArea, width * height);
                }
            }
        }
    }
}

return maxArea;

}

int main() { int T; cin >> T; while (T--) { int m, n, k; cin >> m >> n >> k; vector<string> board(m); for (int i = 0; i < m; ++i) { cin >> board[i]; } cout << getMaxBeautifulRect(board, m, n, k) << endl; } return 0; }