oj.uz

Submission #146852

# Submission time Handle Problem Language Result Execution time Memory
146852 2019-08-26T11:48:46 Z vex Vještica (COCI16_vjestica) C++14
160 / 160
 406 ms 17404 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);
                }
            }
        }
    }

    subsets[0].push_back(0);
    dp[0]=0;


    //cout<<endl;
    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;

          	//cout<<br<<" "<<vel<<" "<<vel2<<endl;
            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
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 3448 KB Output is correct
2 Correct 6 ms 3448 KB Output is correct
3 Correct 6 ms 3448 KB Output is correct
4 Correct 404 ms 17300 KB Output is correct
5 Correct 405 ms 17272 KB Output is correct
6 Correct 405 ms 17336 KB Output is correct
7 Correct 400 ms 17308 KB Output is correct
8 Correct 402 ms 17404 KB Output is correct
9 Correct 395 ms 17304 KB Output is correct
10 Correct 406 ms 17344 KB Output is correct