WHY TLE in atcoder problem helppp

Revision en1, by mainnahihoo, 2025-07-20 00:19:22

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)