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

P.S. It seems like my code is coming out without any kind of spacing. How do I correct this?

include

include

include

include

include

using namespace std; typedef long long ll;

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