oj.uz

Submission #167555

# Submission time Handle Problem Language Result Execution time Memory
167555 2019-12-09T00:39:31 Z combi1k1 Vještica (COCI16_vjestica) C++14
160 / 160
 371 ms 1656 KB 
#include<bits/stdc++.h>

using namespace std;

const int   inf = 0x3f3f3f3f;

vector<int> s[16];

int A[1 << 16];
int f[1 << 16];

int work(int m) {
    if (m == 0)     return  0;
    if (f[m] < inf) return  f[m];

    if (__builtin_popcount(m) == 1)
        return  f[m] = A[m];

    for(int x = m ; x ; x = (x - 1) & m)    if (x ^ m)
        f[m] = min(f[m],work(x) + work(m ^ x) - A[m]);

    return  f[m];
}

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    for(int i = 0 ; i < n ; ++i)    {
        s[i].resize(26);
        string t;   cin >> t;

        for(char c : t)
            s[i][c - 'a']++;
    }

    for(int i = 1 ; i < (1 << n) ; ++i) {
        vector<int> c(26,1e6);
        for(int j = 0 ; j < n ; ++j)    if (i >> j & 1)
        for(int k = 0 ; k < 26 ; ++k)   c[k] = min(c[k],s[j][k]);

        for(int x : c)
            A[i] += x;
    }

    memset(f,0x3f3f3f3f,sizeof f);

    cout << work((1 << n) - 1) + 1 << endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 359 ms 988 KB Output is correct
5 Correct 357 ms 1016 KB Output is correct
6 Correct 359 ms 1212 KB Output is correct
7 Correct 358 ms 1520 KB Output is correct
8 Correct 360 ms 1468 KB Output is correct
9 Correct 371 ms 1428 KB Output is correct
10 Correct 366 ms 1656 KB Output is correct