Scribd
Upload
414 views3 pages

Codeforces Solution

The document contains a C++ program that processes multiple test cases to calculate and modify a grid based on a given path. It computes initial row and column sums while ignoring specific cells, then updates the grid values based on the path traversed. Finally, it outputs the modified grid for each test case.

Uploaded by

Amritansha Sinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
414 views3 pages

Codeforces Solution

The document contains a C++ program that processes multiple test cases to calculate and modify a grid based on a given path. It computes initial row and column sums while ignoring specific cells, then updates the grid values based on the path traversed. Finally, it outputs the modified grid for each test case.

Uploaded by

Amritansha Sinha
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <iostream>

#include <vector>

#include <string>

#include <numeric>

using namespace std;

pair<vector<int>, vector<int>> calculate_initial_sums(const vector<vector<int>>& g, const


vector<vector<bool>>& p, int n, int m) {

vector<int> r_sums(n, 0);

vector<int> c_sums(m, 0);

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

if (!p[i][j]) {

r_sums[i] += g[i][j];

c_sums[j] += g[i][j];

return {r_sums, c_sums};

int main() {

int t;

cin >> t;

while (t--) {

int r, c;

cin >> r >> c;

string ps;

cin >> ps;


vector<pair<int, int>> path;

path.push_back({0, 0});

int row = 0, col = 0;

for (char d : ps) {

if (d == 'D') row++;

else col++;

path.push_back({row, col});

vector<vector<int>> g(r, vector<int>(c));

for (int i = 0; i < r; ++i) {

for (int j = 0; j < c; ++j) {

cin >> g[i][j];

vector<vector<bool>> is_path(r, vector<bool>(c, false));

for (const auto& cell : path) {

is_path[cell.first][cell.second] = true;

auto [initial_r_sums, initial_c_sums] = calculate_initial_sums(g, is_path, r, c);

vector<vector<int>> final_g = g;

for (size_t k = 0; k < path.size() - 1; ++k) {

int r1 = path[k].first;

int c1 = path[k].second;

int r2 = path[k + 1].first;

int c2 = path[k + 1].second;


if (r1 == r2) {

int val = initial_c_sums[c1] - accumulate(final_g[r1].begin(), final_g[r1].end(), 0) +


final_g[r1][c1];

final_g[r1][c1] = val;

} else {

int val = initial_r_sums[r1] - accumulate(final_g[r1].begin(), final_g[r1].end(), 0) +


final_g[r1][c1];

final_g[r1][c1] = val;

if (!path.empty()) {

int last_r = path.back().first;

int last_c = path.back().second;

int val_r = initial_r_sums[last_r] - accumulate(final_g[last_r].begin(), final_g[last_r].end(), 0) +


final_g[last_r][last_c];

final_g[last_r][last_c] = val_r;

for (int i = 0; i < r; ++i) {

for (int j = 0; j < c; ++j) {

cout << final_g[i][j] << (j == c - 1 ? "" : " ");

cout << endl;

return 0;

You might also like