1393D - Rarity and New Dress - CodeForces Solution

#include <iostream>
#include <vector>

void getWatman(std::vector<std::string>& whatman,
    int& whatman_row_count, int& whatman_column_count,
    std::istream& input_stream = std::cin)
{
    input_stream >> whatman_row_count >> whatman_column_count;
    whatman.resize(whatman_row_count);
    for (int row_index = 0; row_index < whatman_row_count; ++row_index) {
        input_stream >> whatman[row_index];
    }
}

int64_t getTheNumberOfWays(const std::vector<std::string>& whatman,
    int whatman_row_count, int whatman_column_count)
{
    int64_t theNumberOfWays = 0;
    const int k_index_offset = 1;

    std::vector<std::vector<int>> count_up(whatman_row_count, std::vector<int>(whatman_column_count, 0));
    for (int row_index = 0; row_index < whatman_row_count; ++row_index) {
        for (int column_index = 0; column_index < whatman_column_count; ++column_index) {
            if (row_index != 0 && whatman[row_index][column_index] == whatman[row_index - k_index_offset][column_index]) {
                count_up[row_index][column_index] = count_up[row_index - k_index_offset][column_index] + k_index_offset;
            }
        }
    }

    std::vector<std::vector<int>> cnt_down(whatman_row_count, std::vector<int>(whatman_column_count, 0));
    for (int row_index = whatman_row_count - k_index_offset; row_index >= 0; --row_index) {
        for (int column_index = 0; column_index < whatman_column_count; ++column_index) {
            if (row_index != whatman_row_count - k_index_offset
                && whatman[row_index][column_index] == whatman[row_index + k_index_offset][column_index])
            {
                cnt_down[row_index][column_index] = cnt_down[row_index + k_index_offset][column_index] + k_index_offset;
            }
        }
    }

    for (int row_index = 0; row_index < whatman_row_count; ++row_index) {
        std::vector<int> left_part(whatman_column_count, 0);
        for (int column_index = 0; column_index < whatman_column_count; ++column_index) {
            int go = column_index;
            while (go < whatman_column_count && whatman[row_index][column_index] == whatman[row_index][go]) {
                go++;
            }
            go--;
            for (int pos = column_index; pos <= go; ++pos) {
                if (pos == column_index) {
                    left_part[pos] = pos;
                }
                else {
                    left_part[pos] = std::max(left_part[pos - k_index_offset], pos - std::min(count_up[row_index][pos], cnt_down[row_index][pos]));
                }
            }
            column_index = go;
        }
        std::vector<int> rigth_part(whatman_column_count, 0);
        for (int column_index = whatman_column_count - k_index_offset; column_index >= 0; --column_index) {
            int go = column_index;
            while (go >= 0 && whatman[row_index][column_index] == whatman[row_index][go]) {
                go--;
            }
            go++;
            for (int pos = column_index; pos >= go; --pos) {
                if (pos == column_index) {
                    rigth_part[pos] = pos;
                }
                else {
                    rigth_part[pos] = std::min(rigth_part[pos + k_index_offset], pos + std::min(count_up[row_index][pos], cnt_down[row_index][pos]));
                }
            }
            column_index = go;
        }
        for (int column_index = 0; column_index < whatman_column_count; ++column_index) {
            theNumberOfWays += std::min(column_index - left_part[column_index] + k_index_offset, rigth_part[column_index] - column_index + k_index_offset);
        }
    }
    return theNumberOfWays;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::vector<std::string> whatman;
    int whatman_row_count = 0;
    int whatman_column_count = 0;
    getWatman(whatman, whatman_row_count, whatman_column_count);

    std::cout << getTheNumberOfWays(whatman, whatman_row_count, whatman_column_count) << std::endl;

    return 0;
}