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!