Approach
make the row and column sums to be equal to zero in other words let $$$x=0$$$ then construct the matrix
- Create two vectors call them as "row_sums" and "col_sums".
$$$RowSums[i]$$$ corresponds to sum of all elements in $$$row_{i}$$$
Same goes for col_sums
given $$$A = n\times m$$$ matrix, where it's always the case that $$$A_{1, 1}=0$$$(one based index), here we have 2 options to go to from $$$A_{1,1}$$$
- Go right
- Go down
Right
Going right indirectly means that $$$A_{i, 1} $$$ where $$$i \in [2, n]$$$ for all $$$i$$$ are never went missing these values are unchanged, find column-1 sum then replace $$$A_{1,1}=0$$$ with $$$A_{1,1}=-\sum_{i=1}^{n}{A_{i, 1}}$$$ since $$$A_{1, 1}=0$$$ we can take summation without having to worry about subtracting $$$A_{1,1}$$$ from the column sum
Then update the col_sums and row_sums array. col_sums[1] += $$$A_{1,1}$$$ and row_sums[1] += $$$A_{1,1}$$$
Update the position of the current indexes based on the next character value that comes from string s. if next character is D then increase the row index by 1. if next character is R update column index by 1.
Down
Going Down indirectly means that $$$A_{1, j} $$$ where $$$j \in [2, m]$$$ for all $$$j$$$ are never went missing these values are unchanged, find row-1 sum then replace $$$A_{1,1}=0$$$ with $$$A_{1,1}=-\sum_{j=1}^{m}{A_{1, j}}$$$ since $$$A_{1, 1}=0$$$ we can take summation without having to worry about subtracting $$$A_{1,1}$$$ from the row sum
Then update the col_sums and row_sums array. col_sums[1] += $$$A_{1,1}$$$ and row_sums[1] += $$$A_{1,1}$$$
Update the position of the current indexes based on the next character value that comes from string s. if next character is D then increase the row index by 1. if next character is R update column index by 1.
Its an integer overflow error since you are using int instead of ll in many places. I just added '#define int long long' in your code and changed 'int main()' to 'signed main()' then it is getting accepted.
But why would an integer overflow would occur, at most n=m=1000 integer can handle it i used long long to initiliaze the matrix even thought it's not needed as the values in the matrix are of range $$$-10^6$$$
to $$$10^6$$$ so it should be fine.
The elements in col_sums or row_sums at most values can be in order of $$$1000.10^6 = 10^9$$$
$$$10^9$$$ takes 30 bits. $$$-1000.10^{6} = -10^{9}$$$ which would take 31 bits. I don't see why an integer overflow would occur?
Edit: How did you know it was integer overflow that was causing the issue?
I literally got wrong answer on pretest 4 in contest because of this issue, but I unknowingly changed int to long long and it worked. I was also thinking why
1e3 * 1e6would exceed integer limit.Very good questions indeed my friends. Here is a test case which can cause integer overflow in both of your submissions:
Test Case:{ n=1000,m=1000 All elements of matrix are 1e6, except for the elements in first row and last column where all elements are 0. } Firstly, problem with submission of dorasainath955:
While moving from cell (0,0) to cell (0,1e3), we can see that every element will we reassigned from 0 to -999*1e6, so when we reach the rightmost cell, the int row_sum variable which you are using will have a value equal to around 999*(-999*1e6) which exceeds the limit of int hence the overflow.
Most of your variables are correctly ll but the ones which involve sum like row_sum, col_sum etc. are int hence overflowing, change them to ll and your solution will pass then you wont need to use '#define int long long'.
Now, problem with TCS_Bhediya may be similar in his first submission as he is using int almost everywhere all of which corrected by using '#define int long long'.
Happy to help you all. Happy Coding :)
EDIT: How I knew Overflow was the issue: 1.The constraints were over the charts in this one. 2.There was a time when 9/10 times the problem in my code was Integer Overflow(insert me crying emoji)
Feel free to ask anything you don't understand anything in my explanation :)