#include #include struct DATA { size_t row; size_t found; }; size_t solve(const std::vector>& terrain, size_t rows, size_t cols, size_t timePoint, std::vector> &cache, std::vector &cache2) { size_t total = 0; for (size_t col = 0; col < cols; col++) { size_t empty_found = 0; size_t col_found = 0; if (cache[col].size() > timePoint) { total += cache[col][timePoint].found; continue; } size_t row = 0; if (cache[col].size() != 0) { col_found = cache[col].back().found; row = cache[col].back().row + 1; empty_found = cache[col].size(); } while (empty_found <= timePoint && row < rows) { if (terrain[rows - row - 1][col] == '.') { empty_found += 1; cache[col].push_back(DATA { row: row, found: col_found }); } else { col_found += 1; } row += 1; } total += col_found; } return total; } std::vector precompute(const std::vector>& terrain, size_t rows, size_t cols, size_t biggestTimePoint) { std::vector output(biggestTimePoint + 1, 0); size_t total = 0; std::vector row_ended = std::vector(cols, 0); for (size_t timePoint = 0; timePoint <= biggestTimePoint; timePoint += 1) { for (size_t col = 0; col < cols; col++) { size_t row = row_ended[col]; while (row < rows) { if (terrain[rows - row - 1][col] == '*') { total += 1; } else { row_ended[col] = row + 1; break; } row += 1; } if (row >= rows) { row_ended[col] = row; } } output[timePoint] = total; } return output; } int main() { size_t rows,cols = 0; size_t inputs = 0; std::ios::sync_with_stdio(false); std::cin >> rows >> cols >> inputs; std::vector> terrain; std::vector timePoints; terrain.reserve(rows); timePoints.reserve(inputs); for (size_t y = 0; y < rows; y++) { terrain.emplace_back(); terrain[y].reserve(cols); for (size_t x = 0; x < cols; x++) { char c = 0; std::cin >> c; terrain[y].push_back(c); } } size_t biggest = 0; for (size_t i = 0; i < inputs; i++) { size_t point = 0; std::cin >> point; timePoints.push_back(point); if (biggest < point) { biggest = point; } } std::vector> cache(cols); std::vector computed = precompute(terrain, rows, cols, biggest); for (auto timePoint : timePoints) { std::cout << computed[timePoint] << std::endl; } }