oj.uz

Submission #167677

# Submission time Handle Problem Language Result Execution time Memory
167677 2019-12-09T12:22:04 Z EntityIT Vještica (COCI16_vjestica) C++14
160 / 160
 184 ms 760 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
#define fi first
#define se second
using LL = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count() );
const int inf = 1e9;

int n;
vector<int> f;
vector<vector<int> > cnt;

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

    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s; cin >> s;
        cnt.emplace_back(vector<int>(26, 0) );

        for (char c : s) ++cnt.back()[c - 'a'];
    }

    f.assign(1 << n, inf);
    f[0] = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        if (__builtin_popcount(mask) == 1) {
            f[mask] = accumulate(all(cnt[__lg(mask)]), 0);
            continue ;
        }

        int tmp = 0;
        for (int ascii = 0; ascii < 26; ++ascii) {
            int mn = inf;
            for (int i = 0; i < n; ++i) if ( (mask >> i) & 1) mn = min(mn, cnt[i][ascii]);
            tmp += mn;
        }

        for (int sMask = mask; sMask > 0; sMask = (sMask - 1) & mask) if (sMask != mask) {
            f[mask] = min(f[mask], f[sMask] + f[mask ^ sMask] - tmp);
        }
    }

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

    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 181 ms 632 KB Output is correct
5 Correct 181 ms 632 KB Output is correct
6 Correct 182 ms 636 KB Output is correct
7 Correct 183 ms 760 KB Output is correct
8 Correct 183 ms 760 KB Output is correct
9 Correct 184 ms 752 KB Output is correct
10 Correct 183 ms 760 KB Output is correct