제출 #736188

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

vjestica

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

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
    inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
    inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 16;

int dp[1 << MAXN], cnt[MAXN + 4][30], tmp[30], numString;

void process() {
    cin >> numString;
    for (int i = 1; i <= numString; ++i) {
        string str;
        cin >> str;

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

    for (int mask = 1; mask < (1 << numString); ++mask) {
        for (int i = 0; i < 26; ++i)
            tmp[i] = 1e9;

        for (int i1 = mask; i1 > 0; i1 ^= i1 & -i1) {
            int i = __builtin_ctz(i1 & -i1) + 1;
            for (int j = 0; j < 26; ++j)
                tmp[j] = min(tmp[j], cnt[i][j]);
        }

        int sum(0);
        for (int i = 0; i < 26; ++i)
            sum += tmp[i];

        if(__builtin_popcount(mask) == 1) {
            dp[mask] = sum;
            continue;
        }

        dp[mask] = 1e9+7;
        for (int maskx = (mask - 1) & mask; maskx > 0; maskx = (maskx - 1) & mask) {
            dp[mask] = min(dp[mask], dp[maskx] + dp[mask ^ maskx] - sum);
        }
    }

    cout << 1 + dp[(1 << numString) - 1];
}

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

    process();
    return 0;
}

• Subtask 1: 160 / 160