Submission #126954

#	Time	Username	Problem	Language	Result	Execution time	Memory
126954		stefdasca	Vještica (COCI16_vjestica)	C++14	0 / 160	2061 ms	9716 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 = 1; j + 1 < (1<<v.size()); ++j)
    {
        int xx = 0;
        for(int q = 0; q < v.size(); ++q)
            if(j & (1<<q))
                xx += (1<<q);
        dp[i] = min(dp[i], solve(xx) + solve(i ^ xx) - 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 solve(int)':
vjestica.cpp:44:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int q = 0; q < v.size(); ++q)
                        ~~^~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:59:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s[i].size(); ++j)
                        ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 160