Submission #146851

#	Time	Username	Problem	Language	Result	Execution time	Memory
146851		vex	Vještica (COCI16_vjestica)	C++14	0 / 160	398 ms	17784 KiB

vjestica

#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 vel2=br-vel;
          	if(vel2>4)vel2=8;
          	else if(vel2>2)vel2=4;
            int sub2=0;
            for(int w=br-1;(br-1)-w+1<=vel2;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: 0 / 160