Submission #126955

#	Time	Username	Problem	Language	Result	Execution time	Memory
126955		stefdasca	Vještica (COCI16_vjestica)	C++14	0 / 160	5 ms	1144 KiB

vjestica

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;

int n, frq[30][30], dp[(1<<17)], viz[(1<<17)];
string s[20];
int prf(int msk)
{
    int mn[28];
    for(int i = 0; i <= 25; ++i)
        mn[i] = (1<<30);
    for(int i = 0; i < n; ++i)
    {
        if(msk & (1<<i))
            for(int j = 0; j <= 25; ++j)
                mn[j] = min(mn[j], frq[i][j]);
    }
    int ans = 0;
    for(int j = 0; j <= 25; ++j)
        ans += mn[j];
    return ans;
}
int solve(int i)
{
    if(viz[i])
        return dp[i];
    viz[i] = 1;
    int x = prf(i);
    vector<int>v;
    for(int j = 0; j < n; ++j)
        if(i & (1<<j))
            v.push_back(j);
    if(v.size() == 1)
    {
        dp[i] = x;
        return dp[i];
    }
    dp[i] = (1<<29);
    for(int j = i & (i-1); j; j = j & (j-1))
        dp[i] = min(dp[i], solve(j) + solve(i ^ j) - x);
    return dp[i];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> s[i];
        for(int j = 0; j < s[i].size(); ++j)
            frq[i][s[i][j] - 'a']++;
    }
    cout << solve((1<<n) - 1) + 1 << '\n';
    return 0;
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:53:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s[i].size(); ++j)
                        ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 160