After going through the tutorial and seeing that an O(m*n) algorithm would pass and there was something to do with a "right" array, I coded up a solution that TLEd and then optimized it over XYZ attempts to this:
http://codeforces.me/contest/376/submission/5630035
which still TLEs. A friend optimized it to traverse in column major: http://codeforces.me/contest/376/submission/5631054
which passes. But, when I do the same:
http://codeforces.me/contest/376/submission/5631820
TLE! Any explanations?
Edit: Solved... (change char[] to string)
When you have two similar solutions, one of which passes and one doesn't, try to find differences.
In this case, try to replace "string" with "char[]" and get AC
Yup, just changed it, thanks :) [Edit: I had somehow not seen the string/char[] difference :| ]
You are reading 25 megabytes of data with cin. Try using scanf or gets to read the data.
I used sync_with_stdio(0); though.
It passed once I changed it to a char array. I guess the overhead with string arrays is too high.