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<fstream>↵
#include<string>↵
#include<vector>↵
#include<iostream>↵
#include <algorithm>↵
using namespace std;↵
typedef long long ll;↵
↵
↵
int main(){↵
ll n,m; [cut]↵
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]↵
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<fstream>↵
#include<string>↵
#include<vector>↵
#include<iostream>↵
#include <algorithm>↵
using namespace std;↵
typedef long long ll;↵
↵
↵
int main(){↵
ll n,m; [cut]↵
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]↵
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]↵
cout << counter; [cut]↵
return 0;
}
} [cut]↵
