oj.uz

Submission #241931

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

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;

        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[smsk] - loc);


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

    rec(0);

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

Subtask #1
48.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 384 KB Output is correct
2 Correct 23 ms 384 KB Output is correct
3 Correct 23 ms 384 KB Output is correct
4 Execution timed out 2093 ms 640 KB Time limit exceeded
5 Execution timed out 2021 ms 640 KB Time limit exceeded
6 Execution timed out 2096 ms 640 KB Time limit exceeded
7 Execution timed out 2085 ms 768 KB Time limit exceeded
8 Execution timed out 2091 ms 640 KB Time limit exceeded
9 Execution timed out 2061 ms 760 KB Time limit exceeded
10 Execution timed out 2079 ms 640 KB Time limit exceeded