Submission #117501

#	Time	Username	Problem	Language	Result	Execution time	Memory
117501		FutymyClone	Vještica (COCI16_vjestica)	C++14	0 / 160	104 ms	1588 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

const int N = 16;

int n, cnt[N][26], temp[26], valmask[1 << N], dp[1 << N], sum[N];

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < s.length(); j++) cnt[i][s[j] - 'a']++;
        sum[i] = s.length();
    }

    for (int mask = 0; mask < (1 << n); mask++) {
        memset(temp, 0x3f, sizeof(temp));
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                for (int j = 0; j < 26; j++) if (cnt[i][j]) temp[j] = min(temp[j], cnt[i][j]);
            }
        }

        for (int i = 0; i < 26; i++) if (temp[i] < 1e9) valmask[mask] += temp[i];
        int res = valmask[mask];
        for (int i = 0; i < n; i++) if (mask & (1 << i)) valmask[mask] += max(0, sum[i] - res);
    }

    memset(dp, 0x3f, sizeof(dp)); dp[0] = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
            dp[mask] = min(dp[mask], dp[mask ^ submask] + valmask[submask]);
        }
    }

    cout << dp[(1 << n) - 1] + 1;
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 160