Submission #248376

#	Time	Username	Problem	Language	Result	Execution time	Memory
248376		Vladikus004	Vještica (COCI16_vjestica)	C++14	160 / 160	304 ms	1656 KiB

vjestica

#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 16;
int n, cnt[N][26], dp[(1<<16) + 3];
string s[N];

int get_pref(int mask){
    int mn[26];
    fill(mn, mn + 26, inf);
    for (int i = 0; i < n; i++){
        if (!((1<<i) & mask)) continue;
        for (int j = 0; j < 26; j++)
            mn[j] = min(mn[j], cnt[i][j]);
    }
    int sum = 0;
    for (int i = 0; i < 26; i++)
        sum += mn[i];
    return sum;
}

int get_ans(int mask){
    if (dp[mask] != -1) return dp[mask];
    int pref = get_pref(mask);
    if (__builtin_popcount(mask) == 1) return pref;
    dp[mask] = inf;
    for (int i = mask & (mask - 1); i > 0; i = (i - 1) & mask)
        dp[mask] = min(dp[mask], get_ans(i) + get_ans(mask^i) - pref);
    return dp[mask];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> s[i];
        for (int j = 0; j < s[i].size(); j++)
            cnt[i][s[i][j] - 'a']++;
    }
    cout << get_ans((1<<n)-1) + 1;
}

Compilation message (stderr)

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

• Subtask 1: 160 / 160