oj.uz

Submission #339112

# Submission time Handle Problem Language Result Execution time Memory
339112 2020-12-24T15:52:49 Z scales Beautiful row (IZhO12_beauty) C++17
100 / 100
 1051 ms 164588 KB 
#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
long long dp[20][1100000];
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        //freopen("b.in","r",stdin);
        //freopen("b.out","w",stdout);
    int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
    long long sum;
    vector<int > d(31),t(21);
    d[0]=1;
    t[0]=1;
    for(i=1;i<=30;i++)
    {
        d[i]=d[i-1]*2;
        //cout<<"d[i]="<<d[i]<<endl;
    }
    for(i=1;i<=18;i++)
    {
        t[i]=t[i-1]*3;
        //cout<<"t["<<i<<"]="<<t[i]<<endl;
    }
    cin>>n;
    vector<int> a(n),b(n),c(n);
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=0;
        c[i]=0;
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<=30;j++)
        {
            z=a[i]&d[j];
            if(z!=0)
            {
                b[i]++;
            }
        }
       // cout<<"b["<<i<<"]="<<b[i]<<endl;
    }
    for(i=0;i<n;i++)
    {
        for(j=18;j>=0;j--)
        {
            //cout<<"a["<<i<<"]="<<a[i]<<endl;
            if(a[i]>=2*t[j])
            {
                a[i]=a[i]-2*t[j];
            }
            else
            {
                if(a[i]>=t[j])
                {
                    c[i]++;
                    a[i]=a[i]-t[j];
                }
            }
        }
       // cout<<"c["<<i<<"]="<<c[i]<<endl;
    }
    //cout<<endl;
    int s[20][20];
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(c[i]==c[j] || b[i]==b[j])
            {
                s[i][j]=1;
            }
            else
            {
                s[i][j]=0;
            }
            //cout<<s[i][j]<<" ";
        }
        //cout<<endl;
    }
    for(i=0;i<n;i++)
    {
        dp[i][0]=0;
    }
    for(j=1;j<d[n];j++)
    {
        for(i=0;i<n;i++)
        {
                if(j==d[i])
                {
                    dp[i][j]=1;
                }
                else
                {
                    dp[i][j]=0;
                    z=j&d[i];
                    if(z!=0)
                    {
                        x=j-d[i];
                        //cout<<"x="<<x<<" ";
                        for(q=0;q<n;q++)
                        {
                            if(q!=i && s[q][i]==1)
                            {
                                z=j&d[q];
                                if(z!=0)
                                {
                                    dp[i][j]=dp[i][j]+dp[q][x];
                                }
                            }
                        }
                    }
                }
                //cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
        }
    }
    sum=0;
    for(i=0;i<n;i++)
    {
        sum=sum+dp[i][d[n]-1];
    }
    cout<<sum<<endl;



    return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:16:13: warning: unused variable 'y' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |             ^
beauty.cpp:16:17: warning: unused variable 'm' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                 ^
beauty.cpp:16:19: warning: unused variable 'k' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                   ^
beauty.cpp:16:21: warning: unused variable 'x1' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                     ^~
beauty.cpp:16:24: warning: unused variable 'g' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                        ^
beauty.cpp:16:26: warning: unused variable 'y1' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                          ^~
beauty.cpp:16:33: warning: unused variable 'f' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                 ^
beauty.cpp:16:35: warning: unused variable 'l' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                   ^
beauty.cpp:16:39: warning: unused variable 'maxi' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                       ^~~~
beauty.cpp:16:44: warning: unused variable 'r' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                            ^
beauty.cpp:16:46: warning: unused variable 'kol' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                              ^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 10 ms 2284 KB Output is correct
12 Correct 10 ms 2284 KB Output is correct
13 Correct 47 ms 8604 KB Output is correct
14 Correct 229 ms 37440 KB Output is correct
15 Correct 214 ms 37356 KB Output is correct
16 Correct 211 ms 37356 KB Output is correct
17 Correct 218 ms 37484 KB Output is correct
18 Correct 184 ms 37356 KB Output is correct
19 Correct 1051 ms 164588 KB Output is correct
20 Correct 987 ms 164588 KB Output is correct