제출 #167677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
167677		EntityIT	Vještica (COCI16_vjestica)	C++14	160 / 160	184 ms	760 KiB

vjestica

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
#define fi first
#define se second
using LL = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() );
const int inf = 1e9;

int n;
vector<int> f;
vector<vector<int> > cnt;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        cnt.emplace_back(vector<int>(26, 0) );

        for (char c : s) ++cnt.back()[c - 'a'];
    }

    f.assign(1 << n, inf);
    f[0] = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) == 1) {
            f[mask] = accumulate(all(cnt[__lg(mask)]), 0);
            continue ;
        }

        int tmp = 0;
        for (int ascii = 0; ascii < 26; ++ascii) {
            int mn = inf;
            for (int i = 0; i < n; ++i) if ( (mask >> i) & 1) mn = min(mn, cnt[i][ascii]);
            tmp += mn;
        }

        for (int sMask = mask; sMask > 0; sMask = (sMask - 1) & mask) if (sMask != mask) {
            f[mask] = min(f[mask], f[sMask] + f[mask ^ sMask] - tmp);
        }
    }

    cout << f[(1 << n) - 1] + 1;

    return 0;
}

• Subtask 1: 160 / 160