제출 #241930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
241930		Vimmer	Vještica (COCI16_vjestica)	C++14	48 / 160	2090 ms	768 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)];

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);

    int n;

    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 = 1; msk < (1 << n); msk++)
    {
        vector <int> pr; pr.clear();

        for (int i = 0; i < n; i++)
            if (!((1 << i) & msk)) pr.pb(i);

        for (int smsk = 1; smsk < (1 << sz(pr)); smsk++)
        {
            int nmsk = msk, mask = 0;

            for (int i = 0; i < sz(pr); i++)
                if ((1 << i) & smsk) {nmsk |= (1 << pr[i]); mask |= (1 << pr[i]);}

            int loc = 0;

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

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

                loc += mn;
            }

            f[nmsk] = min(f[nmsk], f[msk] + f[mask] - loc);
        }
    }

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

• Subtask 1: 48 / 160