Submission #1140807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140807		12345678	Vještica (COCI16_vjestica)	C++20	160 / 160	83 ms	584 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

const int nx=16, kx=30;

int n, cnt[nx][kx], dp[1<<nx];
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=0; i<n; i++)
    {
        cin>>s;
        for (auto x:s) cnt[i][x-'a']++; 
    }
    for (int msk=1; msk<(1<<n); msk++)
    {
        int cur=0;
        for (int c=0; c<26; c++)
        {
            int mn=1e9;
            for (int i=0; i<n; i++) if (msk&(1<<i)) mn=min(mn, cnt[i][c]);
            cur+=mn;
        }
        if (__builtin_popcount(msk)==1)
        {
            dp[msk]=cur;
            continue;
        }
        dp[msk]=1e9;
        for (int sub=msk; sub>0; sub=(sub-1)&msk) dp[msk]=min(dp[msk], dp[sub]+dp[msk^sub]-cur);
    }
    //for (int msk=0; msk<(1<<n); msk++) cout<<"debug "<<msk<<' '<<dp[msk]<<'\n';
    cout<<dp[(1<<n)-1]+1;
}

• Subtask 1: 160 / 160