oj.uz

Submission #998844

# Submission time Handle Problem Language Result Execution time Memory
998844 2024-06-14T17:55:43 Z fryingduc Vještica (COCI16_vjestica) C++17
160 / 160
 74 ms 1212 KB 
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e6 + 6;
const int inf = 1e9;
const int MASK = (1 << 16) + 5;

int n;
int cnt[20][26];
int f[MASK];

bool check() {
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 26; ++j) {
            if(cnt[i][j]) return 0;
        }
    }
    return 1;
}
void solve() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for(auto &j:s) {
            cnt[i][j - 'a']++;
        }
    }
    for(int mask = 0; mask < (1 << n); ++mask) {
        int sum = 0;
        vector<int> v(26, inf);
        for(int i = 1; i <= n; ++i) {
            if(mask >> (i - 1) & 1) {
                for(int j = 0; j < 26; ++j) {
                    v[j] = min(v[j], cnt[i][j]);                    
                }
            }
        }
        for(int i = 0; i < 26; ++i) {
            sum += v[i];
        }
        
        f[mask] = inf;
        if(__builtin_popcount(mask) == 1) {
            f[mask] = sum;
        }
        for(int sub_mask = (mask - 1) & mask; sub_mask > 0; sub_mask = (sub_mask - 1) & mask) {
            f[mask] = min(f[mask], f[sub_mask] + f[mask ^ sub_mask] - sum);
        }
    }
    cout << f[(1 << n) - 1] + 1;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 74 ms 632 KB Output is correct
5 Correct 71 ms 600 KB Output is correct
6 Correct 71 ms 856 KB Output is correct
7 Correct 71 ms 1100 KB Output is correct
8 Correct 71 ms 1108 KB Output is correct
9 Correct 72 ms 1104 KB Output is correct
10 Correct 71 ms 1212 KB Output is correct