제출 #241457

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

vjestica

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define i2 array<int,2>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
const int N = 16;
const int M = 100100;
const int AL = 26;
const int PW = (1 << 16);
const int oo = 2e9;
string s;
int cnt[N][AL], f[PW], eco[PW], mn[AL], n;

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

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> s;

        for (int j = 0; j < sz(s); j++)
            cnt[i][s[j] - 'a']++;
    }

    for (int msk = 1; msk < (1 << n); msk++){
        fill(mn, mn + AL, oo);

        for (int i = 0; i < n; i++)
            if (msk & (1 << i)){
                for (int j = 0; j < 26; j++)
                    mn[j] = min(mn[j], cnt[i][j]);
            }

        for (int j = 0; j < 26; j++)
            eco[msk] += mn[j];
    }

    for (int msk = 1; msk < (1 << n); msk++)
        if (__builtin_popcount(msk) == 1)
            f[msk] = eco[msk];
        else {
            f[msk] = oo;

            for (int sub = ((msk - 1) & msk); sub > 0; sub = (sub - 1) & msk){
                f[msk] = min(f[msk], f[sub] + f[msk ^ sub] - eco[msk]);
            }
        }

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

    return 0;
}

• Subtask 1: 160 / 160