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; 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; }