제출 #241932

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

vjestica

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 1000501
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9


using namespace std;
//using namespace __gnu_pbds;
typedef long double ld;
typedef long long ll;
typedef short int si;
typedef array <int, 3> a3;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int a[20][26], f[(1 << 16)], n, val[20], cost[(1 << 16)];

void rec(int v)
{
    if (v == n)
    {
        int msk = 0, smsk = 0;

        for (int i = 0; i < n; i++)
          if (val[i] == 1) msk |= (1 << i);
            else if (val[i] == 2) smsk |= (1 << i);

        int nmsk = msk ^ smsk;

        f[nmsk] = min(f[nmsk], f[msk] + f[smsk] - cost[nmsk]);


        return;
    }

    for (int j = 0; j < 3; j++)
    {
        val[v] = j;

        rec(v + 1);
    }
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int msk = 0; msk < (1 << n); msk++) f[msk] = 1e9;

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

        cin >> s;

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

        f[(1 << i)] = sz(s);
    }

    for (int msk = 0; msk < (1 << n); msk++)
        for (int j = 0; j < 26; j++)
        {
            int mn = 1e9;

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

            cost[msk] += mn;
        }

    rec(0);

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

• Subtask 1: 160 / 160