제출 #998844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
998844		fryingduc	Vještica (COCI16_vjestica)	C++17	160 / 160	74 ms	1212 KiB

vjestica

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

const int maxn = 1e6 + 6;
const int inf = 1e9;
const int MASK = (1 << 16) + 5;

int n;
int cnt[20][26];
int f[MASK];

bool check() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 26; ++j) {
            if(cnt[i][j]) return 0;
        }
    }
    return 1;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for(auto &j:s) {
            cnt[i][j - 'a']++;
        }
    }
    for(int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0;
        vector<int> v(26, inf);
        for(int i = 1; i <= n; ++i) {
            if(mask >> (i - 1) & 1) {
                for(int j = 0; j < 26; ++j) {
                    v[j] = min(v[j], cnt[i][j]);                    
                }
            }
        }
        for(int i = 0; i < 26; ++i) {
            sum += v[i];
        }
        
        f[mask] = inf;
        if(__builtin_popcount(mask) == 1) {
            f[mask] = sum;
        }
        for(int sub_mask = (mask - 1) & mask; sub_mask > 0; sub_mask = (sub_mask - 1) & mask) {
            f[mask] = min(f[mask], f[sub_mask] + f[mask ^ sub_mask] - sum);
        }
    }
    cout << f[(1 << n) - 1] + 1;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

• Subtask 1: 160 / 160