WHY TLE in atcoder problem helppp

Revision en2, by mainnahihoo, 2025-07-20 00:33:46

problem atcoder problem

int dp[(1<<20)];
// int cnt=0;
int rec(int mask,string &s,int n){
	// cout<<"call for "<<mask<<endl;
	if(mask==(1<<n)-1)return 1;
	if(dp[mask]!=-1)return dp[mask];
	int x=0;
	for(int i=0;i<n;i++){
		if(!(mask&(1<<i)) && s[mask|(1<<i)]=='0'){
			x|=rec(mask|(1<<i),s,n);
		}
	}
	// cnt++;
	return dp[mask]=x;
}

void solve() {
	// executing code from here 
	int t;
	cin >> t;
	while (t--) {
		int n;cin >> n;string s;cin>>s;
		memset(dp,-1,sizeof(dp));
		s='0'+s;
		if(rec(0,s,n))cy;
		else cn;
	}
}

I am getting TLE why after dp time complexity should be 2^n*n not n!*n

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mainnahihoo 2025-07-20 00:33:46 22
en1 English mainnahihoo 2025-07-20 00:19:22 720 Initial revision (published)