Hi All I'm getting a timeout error for this question. As far as I can tell my algorithm is the same as the one in the tutorial and it's implemented in C++ so I'm at a loss for why it's not fast enough. Moreover when I change from reading in the input to automatically generating an input the same size it takes 13ms and the question allows 1000ms/1s.

In practise I'm reading through the rows of a 1000x1000 matrix one at a time and then the columns one at a time. In my head this should be about 2 million operations (I've heard 10^9 is usually the upper limit to avoid).

My code is below. Any help would be greatly appreciated.

Jon

include

include

include

include

include

using namespace std; typedef long long ll;

int main(){ ll n,m; cin >>n >>m; [cut] ll A[n][m]; [cut] for (ll i=0;i<n;i++){ [cut] for (ll j=0;j<m;j++){ [cut] cin >> A[i][j]; [cut] } [cut] } [cut] A[0][0]=1; [cut] ll counter=0; [cut] for (ll x=0;x<n;x++){ [cut] ll ones=0; [cut] ll firstone=-1; [cut] ll lastone=-1; [cut] for (ll y=0;y<m;y++){ [cut] if (A[x][y]==1){ [cut] if (firstone==-1){ [cut] firstone=y+1; [cut] } [cut] lastone=y+1; [cut] ones++; [cut] } [cut] } [cut] if (firstone>0){ [cut] counter=counter+(lastone-ones)+(m-(firstone-1)-ones); [cut] } [cut] } [cut] for (ll y=0;y<m;y++){ [cut] ll ones=0; [cut] ll firstone=-1; [cut] ll lastone=-1; [cut] for (ll x=0;x<n;x++){ [cut] if (A[x][y]==1){ [cut] if (firstone==-1){ [cut] firstone=x+1; [cut] } [cut] lastone=x+1; [cut] ones++; [cut] } [cut] } [cut] if (firstone>0){ [cut] counter=counter+(lastone-ones)+(n-(firstone-1)-ones); [cut] } [cut] } [cut] cout << counter; [cut] return 0; [cut] } [cut]