oj.uz

Submission #241928

# Submission time Handle Problem Language Result Execution time Memory
241928 2020-06-26T11:10:49 Z Vimmer Vještica (COCI16_vjestica) C++14
48 / 160
 2000 ms 1152 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)];

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++)
    {
        for (int i = 0; i < n; i++)
        {
            if ((1 << i) & msk) continue;

            int nmsk = msk | (1 << i);

            int loc = 0;

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

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

                loc += mn;
            }

            f[nmsk] = min(f[nmsk], f[msk] + f[(1 << i)] - loc);
        }
    }

    for (int msk = 1; msk < (1 << n); msk++)
    {
        int nmsk = msk ^ ((1 << n) - 1);

        int loc = 0;

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

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

            loc += mn;
        }

        f[(1 << n) - 1] = min(f[(1 << n) - 1], f[nmsk] + f[msk] - loc);
    }

    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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 384 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 22 ms 384 KB Output is correct
4 Execution timed out 2080 ms 640 KB Time limit exceeded
5 Execution timed out 2090 ms 768 KB Time limit exceeded
6 Execution timed out 2088 ms 896 KB Time limit exceeded
7 Execution timed out 2086 ms 1148 KB Time limit exceeded
8 Execution timed out 2085 ms 1152 KB Time limit exceeded
9 Execution timed out 2089 ms 1144 KB Time limit exceeded
10 Execution timed out 2078 ms 1152 KB Time limit exceeded