oj.uz

Submission #241932

# Submission time Handle Problem Language Result Execution time Memory
241932 2020-06-26T11:17:57 Z Vimmer Vještica (COCI16_vjestica) C++14
160 / 160
 1317 ms 1140 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 7 ms 256 KB Output is correct
4 Correct 1288 ms 888 KB Output is correct
5 Correct 1317 ms 960 KB Output is correct
6 Correct 1296 ms 1016 KB Output is correct
7 Correct 1296 ms 1140 KB Output is correct
8 Correct 1294 ms 1016 KB Output is correct
9 Correct 1305 ms 1112 KB Output is correct
10 Correct 1289 ms 1016 KB Output is correct