제출 #1097099

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

vjestica

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    int frq[n][26] = {}, dp[1 << n];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        dp[1 << i] = s.size();
        for (char c : s) frq[i][c - 'a'] ++;
    }

    for (int mask = 3; mask < 1 << n; mask++) {
        if (bitcount(mask) == 1) continue;
        dp[mask] = 1e9;
        int s = mask;
        while (s > 0) {
            dp[mask] = min(dp[mask], dp[s] + dp[mask ^ s]);
            s = (s - 1) & mask;
        }
        int common = 0;
        for (int c = 0; c < 26; c++) {
            int mn = 1e9;
            for (int i = 0; i < n; i++) if ((mask >> i) & 1) {
                mn = min(mn, frq[i][c]);
            }
            common += mn;
        }
        dp[mask] -= common;
    }
    cout << dp[(1 << n) - 1] + 1;
}

• Subtask 1: 160 / 160