could anyone tell me why code 1 is slower than the second code-
Code:
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define REP(i,n) for(i=0;i<n;++i)
#define FOREACH(it,c) for(typeof((c).begin()) it=(c).begin();it!=(c).end();++it)
using namespace std;
vector <string> rel;
vector <long long> sums(51,0),used(51,0);
class CorporationSalary {
public:
long long calc(int i)
{
long long sum=0,j;
REP(j,sz(rel[0]))
{
if(rel[i][j]=='Y')
{
if(!used[j])
sums[j]=calc(j);
sum+=sums[j];
}
}
if(sum==0)
{
sums[i]=1;
used[i]=1;
return 1;
}
else
{
used[i]=1;
return sum;
}
}
long long totalSalary(vector <string>);
};
long long CorporationSalary::totalSalary(vector <string> relations) {
long long sum=0,i;
rel.resize(sz(relations));
copy(all(relations),rel.begin());
REP(i,sz(relations))
{
sum+=calc(i);
}
return sum;
}
code 2
Code:
#define FOR(i,a,b) for(typeof(a) i=a;i!=b;i++)
#define REP(i,n) FOR(i,0,n)
#define EACH(x,v) for(typeof(v.begin()) x=v.begin();x!=v.end();x++)
#define EXISTS(f,x) ({int _=0; f if(x) _=1;_;})
#define pb push_back
#define mp make_pair
using namespace std;
class CorporationSalary {
public:
long long totalSalary(vector <string>);
};
long long dp[50];
long long foo(int i,vector<string> relations)
{
long long ans=0;
REP(k,relations[i].length()) if(relations[i][k]=='Y'){ if(dp[k]!=-1) ans+=dp[k]; else {dp[k] = foo(k,relations); ans+=dp[k];} }
return ans==0? 1:ans;
}
long long CorporationSalary::totalSalary(vector <string> relations) {
memset(dp,-1,sizeof(dp));
long long sal = 0;
int n = relations.size();
REP(i,n) sal += foo(i,relations);
return sal;
}
the first code to the best of my knowledge uses the same technique as the second but it does not complete some of the larger test cases in time.
cheers!