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<fstream>↵
#include<string>↵
#include<vector>↵
#include<iostream>↵
#include <algorithm>↵
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;↵
}↵
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<fstream>↵
#include<string>↵
#include<vector>↵
#include<iostream>↵
#include <algorithm>↵
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;↵
}↵
