oj.uz

Submission #1097098

# Submission time Handle Problem Language Result Execution time Memory
1097098 2024-10-06T04:07:29 Z SulA Vještica (COCI16_vjestica) C++17
160 / 160
 84 ms 1360 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define bitcount __builtin_popcountll
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<long long,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    int frq[n][26] = {}, dp[1 << n];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        dp[1 << i] = s.size();
        for (char c : s) frq[i][c - 'a'] ++;
    }

    for (int mask = 3; mask < 1 << n; mask++) {
        if (bitcount(mask) == 1) continue;
        dp[mask] = 1e9;
        int s = mask;
        while (s > 0) {
            dp[mask] = min(dp[mask], dp[s] + dp[mask ^ s]);
            s = (s - 1) & mask;
        }
        int common = 0;
        for (int c = 0; c < 26; c++) {
            int mn = 1e9;
            for (int i = 0; i < n; i++) if ((mask >> i) & 1) {
                mn = min(mn, frq[i][c]);
            }
            common += mn;
        }
        dp[mask] -= common;
    }
    cout << dp[(1 << n) - 1] + 1;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 352 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 79 ms 708 KB Output is correct
5 Correct 79 ms 600 KB Output is correct
6 Correct 79 ms 1000 KB Output is correct
7 Correct 84 ms 1116 KB Output is correct
8 Correct 80 ms 1240 KB Output is correct
9 Correct 80 ms 1112 KB Output is correct
10 Correct 80 ms 1360 KB Output is correct