Submission #1226371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226371		VMaksimoski008	Vještica (COCI16_vjestica)	C++20	160 / 160	81 ms	584 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n; cin >> n;
    int a[n][26];

    for(int i=0; i<n; i++) {
        string s; cin >> s;
        for(int j=0; j<26; j++) a[i][j] = 0;
        for(char ch : s) a[i][ch-'a']++;
    }

    vector<int> dp(1<<n, 1e9);
    for(int i=0; i<n; i++) {
        dp[1<<i] = 0;
        for(int j=0; j<26; j++)
            dp[1<<i] += a[i][j];
    }

    for(int s=1; s<(1<<n); s++) {
        if(__builtin_popcount(s) == 1) continue;
        int len = 0;
        for(int j=0; j<26; j++) {
            int mn = 1e9;
            for(int i=0; i<n; i++)
                if(s & (1 << i)) mn = min(mn, a[i][j]);
            len += mn;
        } 

        for(int s2=s&(s-1); s2; s2=s&(s2-1))
            dp[s] = min(dp[s], dp[s2] + dp[s^s2] - len);
    }

    cout << dp[(1<<n)-1] + 1 << '\n';
}

• Subtask 1: 160 / 160