oj.uz

Submission #946550

# Submission time Handle Problem Language Result Execution time Memory
946550 2024-03-14T18:24:58 Z sondos225 Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 172888 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define yes "YES"
#define no "NO"
#define bigg INT_MAX
#define debug(x) cout<<(#x)<<" = " <<x<<endl;
#define all(x) x.begin(),x.end()
#define sz size()
#define nn '\n'
#define mms(x,y) memset(x,y,sizeof(x))
#define forr(i,j,n) for (int i=j; i<n; i++)
#define forn(i,j,n) for (int i=j; i>n; i--)
#define fi first
#define se second
#define la "LA"
#define cinn(x,y) for(int i=0; i<y; i++) cin>>x[i];
#define pii pair<int,int>
unordered_map<int,int> m2;
unordered_map<int,int> m3;
int n;
int dp[21][(1<<20)];
int dfs(int x, int mask)
{
   if (mask==((1<<n)-1)) return 1;
   if (dp[x][mask]!=-1) return dp[x][mask];
   int c=0;
   forr(i,0,n)
   {
       if (m2[x]==m2[i] || m3[x]==m3[i]){
       if (!((1<<i)&mask))
       {
           mask|=(1<<i);
           c+=dfs(i,mask);
           mask^=(1<<i);
       }
       }
   }
   return dp[x][mask]=c;
}
signed main()
{
//    #ifndef LOCAL
//    freopen("lifeguards.in","r",stdin);
//    freopen("lifeguards.out","w", stdout);
//    #endif
    fast
   // int n;
    cin>>n;
    int a[n];
    mms(dp,-1);
    forr(i,0,n)
    {
        cin>>a[i];
        int x=a[i];
        while(x>0)
        {
            if (x%2==1) m2[i]++;
            x/=2;
        }
        x=a[i];
        while(x>0)
        {
            if (x%3==1) m3[i]++;
            x/=3;
        }
    }
    int ans=0;
    forr(i,0,n)
    {
        ans+=dfs(i,(1<<i));
    }
    cout<<ans;
    return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 20 ms 172732 KB Output is correct
3 Correct 21 ms 172636 KB Output is correct
4 Correct 22 ms 172716 KB Output is correct
5 Correct 21 ms 172624 KB Output is correct
6 Correct 22 ms 172548 KB Output is correct
7 Correct 22 ms 172720 KB Output is correct
8 Correct 21 ms 172628 KB Output is correct
9 Correct 24 ms 172628 KB Output is correct
10 Correct 22 ms 172552 KB Output is correct
11 Correct 41 ms 172800 KB Output is correct
12 Correct 37 ms 172636 KB Output is correct
13 Correct 128 ms 172732 KB Output is correct
14 Correct 742 ms 172884 KB Output is correct
15 Correct 841 ms 172796 KB Output is correct
16 Correct 646 ms 172796 KB Output is correct
17 Correct 872 ms 172888 KB Output is correct
18 Correct 570 ms 172880 KB Output is correct
19 Execution timed out 3064 ms 172628 KB Time limit exceeded
20 Halted 0 ms 0 KB -