I solved the question. However, I feel my solution is very inefficient since I just brute forced my way through the question. My solution is here.
Could someone provide a much better and efficient approach?
Your solution is not brute force. It has complexity \mathcal{O}(NM), which is of course optimal since just taking input requires that much.
There is just one issue with your code, you are using long to store the sums. The maximum value attainable by the sum variable is 10^9 \cdot 500 = 5 \cdot 10^{11}. By the C++ standard, a long is guaranteed to be at least 32 bits. However, 32 bits are not sufficient to hold the above value and overflow would occur. It happens to be that on the CodeChef judge, long has 64 bits, so your solution works as intended. You should be using the long long type instead.
1 Like
Oh wow, I did not know that. Thank you so much!
I thought there might be a more efficient way to solve the problem but yeah I do suppose it is O(NM) which is optimal.
Yes, please give editorial of it. I pinged setter on CF but he seems to be not interested in replying me.