Submission #164359

#	Time	Username	Problem	Language	Result	Execution time	Memory
164359		_qVp_	Vještica (COCI16_vjestica)	C++14	160 / 160	319 ms	1524 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

const int md = (1 << 16) + 10;
const int oo = 1e9;

int memo[md], cnt[30][30], common[md], d[30];
int n;

int getbit(int x, int i) {
    return ((x >> i) & 1);
}

int dp(int mask) {
    if (memo[mask] != -1)
        return memo[mask];
    if (__builtin_popcount(mask) == 1)
        return memo[mask] = common[mask];
    int res = oo;
    for(int s = mask & (mask - 1); s; s = (s - 1) & mask) 
        res = min(res, dp(s) + dp(mask ^ s) - common[mask]);
    return memo[mask] = res;
}

int main() {
    //freopen("test.in", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < s.size(); j++)
            cnt[i][s[j] - 'a']++;
    }

    for(int mask = 0; mask < (1 << n); mask++) {
        for(int i = 0; i < 26; i++)
            d[i] = oo;
        for(int i = 0; i < n; i++)
            if (getbit(mask, i)) {
                for(int j = 0; j < 26; j++)
                    d[j] = min(d[j], cnt[i][j]);
            }
        for(int i = 0; i < 26; i++)
            common[mask] += d[i];
    }

    memset(memo, -1, sizeof memo);
    //return 0;
    cout << dp((1 << n) - 1) + 1;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 160 / 160