oj.uz

Submission #685722

# Submission time Handle Problem Language Result Execution time Memory
685722 2023-01-24T22:08:30 Z Summers Beautiful row (IZhO12_beauty) C++14
100 / 100
 2107 ms 189104 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
long long a[100], b[100], dp[(1<<20)][23], n;

long long rec(long long mask, long long last)
{
    if(mask==((1<<n)-1)) return 1;

    if(last!=-1 && dp[mask][last]!=-1)return dp[mask][last];
    long long an=0;
    for(long long i=0;i<n;i++)
    {
        if(!(mask&(1<<i)))
        {
            if(last==-1 || a[last]==a[i] || b[last]==b[i])
            {
                an+=rec(mask|(1<<i), i);
            }
        }
    }
    return dp[mask][last]=an;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long i,j,t,p,p1, ans=0;

    cin>>n;

    for(i=0;i<n;i++)
    {
        cin>>p;
        a[i]=__builtin_popcount(p);
        p1=p;
        while(p1>0)
        {
            if(p1%3==1)b[i]++;
            p1/=3;
        }

    }
    memset(dp,-1,sizeof(dp));
    ans+=rec(0,-1);

    cout<<ans<<endl;


}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:31:17: warning: unused variable 'j' [-Wunused-variable]
   31 |     long long i,j,t,p,p1, ans=0;
      |                 ^
beauty.cpp:31:19: warning: unused variable 't' [-Wunused-variable]
   31 |     long long i,j,t,p,p1, ans=0;
      |                   ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 189028 KB Output is correct
2 Correct 68 ms 189072 KB Output is correct
3 Correct 68 ms 189024 KB Output is correct
4 Correct 67 ms 189000 KB Output is correct
5 Correct 72 ms 189076 KB Output is correct
6 Correct 70 ms 189064 KB Output is correct
7 Correct 70 ms 189104 KB Output is correct
8 Correct 68 ms 189068 KB Output is correct
9 Correct 78 ms 189028 KB Output is correct
10 Correct 69 ms 189068 KB Output is correct
11 Correct 91 ms 189088 KB Output is correct
12 Correct 78 ms 189084 KB Output is correct
13 Correct 129 ms 189040 KB Output is correct
14 Correct 353 ms 189080 KB Output is correct
15 Correct 369 ms 189084 KB Output is correct
16 Correct 308 ms 189004 KB Output is correct
17 Correct 367 ms 189092 KB Output is correct
18 Correct 256 ms 189024 KB Output is correct
19 Correct 1976 ms 189088 KB Output is correct
20 Correct 2107 ms 189084 KB Output is correct