oj.uz

Submission #146844

# Submission time Handle Problem Language Result Execution time Memory
146844 2019-08-26T11:31:28 Z vex Vještica (COCI16_vjestica) C++14
48 / 160
 2000 ms 17784 KB 
#include<bits/stdc++.h>
#define maxn 17
#define INF 10000000
using namespace std;

int n;
int duz[maxn];
int sl[maxn][26];
int dp[(1<<maxn) + 5];
vector<int>sz[maxn];
vector<int>tre;
int minn[26];
string s;
vector<int>subsets[(1<<(maxn))+5];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        duz[i]=s.size();
        for(auto x:s)
        {
            sl[i][x-'a']++;
        }
    }

    for(int i=1;i<(1<<n);i++)
    {
        int sub1=0;
        int sub2=0;

        int br=0;
        for(int j=1;j<=i;j*=2)
        {
            if(j & i)
            {
                if(br%2==0)sub1+=j;
                else sub2+=j;
                br++;
            }
        }
        sz[br].push_back(i);

        if(br==1)
        {
            subsets[i].push_back(0);
            subsets[i].push_back(sub1);
        }

        else if(br==2 || br==4 || br==8)
        {
            for(auto subsub1:subsets[sub1])
            {
                for(auto subsub2:subsets[sub2])
                {
                    subsets[i].push_back(subsub1|subsub2);
                }
            }
        }
    }


    for(int br=1;br<=n;br++)
    {
        for(auto subset:sz[br])
        {
            tre.clear();
            for(int j=0;j<n;j++)
            {
                if((1<<j)&subset)tre.push_back(j);
            }

            if(br==1)
            {
                dp[subset]=duz[tre[0]];
                continue;
            }

            for(int j=0;j<26;j++)minn[j]=INF;
            for(int j=0;j<br;j++)
            {
                for(int w=0;w<26;w++)
                {
                    minn[w]=min(minn[w],sl[ tre[j] ][w]);
                }
            }
            int presek=0;
            for(int j=0;j<26;j++)presek+=minn[j];





            dp[subset]=INF;

            ///SPEED UP
            /*for(int j=1;j<(1<<br)-1;j++)
            {
                int subsub1=0;
                int subsub2=0;

                for(int w=0;w<br;w++)
                {
                    if(j&(1<<w))subsub1+=1<<(tre[w]);
                    else subsub2+=1<<(tre[w]);
                }

                dp[subset]=min(dp[subset],dp[subsub1]+dp[subsub2]-presek);
            }*/

            int vel;
            if(br>=8)vel=8;
            else if(br>=4)vel=4;
            else if(br>=2)vel=2;

            int sub1=0;
            for(int w=0;w<vel;w++)
            {
                sub1+=1<<(tre[w]);
            }

            int sub2=0;
            for(int w=br-1;(br-1)-w+1<=vel;w--)
            {
                sub2+=1<<(tre[w]);
            }

            for(auto subsub1:subsets[sub1])
                for(auto subsub2:subsets[sub2])
                {
                    int sss1=subsub1|subsub2;
                    int sss2=subset-sss1;

                    if(sss1!=0 && sss2!=0)dp[subset]=min(dp[subset],dp[sss1]+dp[sss2]-presek);
                }
        }
    }

    cout<<dp[(1<<n)-1]+1<<endl;
    return 0;
}

Subtask #1
48.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3576 KB Output is correct
2 Correct 27 ms 3448 KB Output is correct
3 Correct 17 ms 3448 KB Output is correct
4 Execution timed out 2029 ms 17272 KB Time limit exceeded
5 Execution timed out 2057 ms 17272 KB Time limit exceeded
6 Execution timed out 2035 ms 17528 KB Time limit exceeded
7 Execution timed out 2013 ms 17656 KB Time limit exceeded
8 Execution timed out 2059 ms 17656 KB Time limit exceeded
9 Execution timed out 2095 ms 17784 KB Time limit exceeded
10 Execution timed out 2091 ms 17656 KB Time limit exceeded