oj.uz

Submission #264108

# Submission time Handle Problem Language Result Execution time Memory
264108 2020-08-14T05:07:57 Z ttnhuy313 Vještica (COCI16_vjestica) C++14
160 / 160
 228 ms 1912 KB 
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, int> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 20;
const int MAXM = 1000010;
const int MAXK = 110;
const int MAXQ = 200010;

int n, cnt[MAXN][26], tmpCnt[26], common[70000], dp[70000];
string s[MAXN];

int solve(int mask) {
    if (dp[mask] != -1) return dp[mask];
    int cm = common[mask];
    int res = 1000000000;
    // submask iteration
    for (int split = mask & (mask-1); split; split = (split-1) & mask) {
        int submask2 = mask ^ split;
        res = min(res, solve(split) + solve(submask2) - cm);
    }
    return dp[mask] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    FOR(i,1,n) cin >> s[i];

    FOR(i,1,n)
        FOR(j,0,SZ(s[i])-1) cnt[i][s[i][j] - 'a']++;

    // get number of same characters in each group of string based on the mask
    FOR(mask,1,(1<<n)-1) {
        FOR(i,0,25) tmpCnt[i] = 1000000000;
        FOR(i,1,n)
            if (mask & (1<<(i-1)))
                FOR(j,0,25) tmpCnt[j] = min(tmpCnt[j], cnt[i][j]);
        FOR(i,0,25) common[mask] += tmpCnt[i];
    }

    // init dp
    FOR(i,1,(1<<n)-1) {
        if (__builtin_popcount(i) == 1) {
            FOR(j,1,n)
                if (i & (1<<(j-1))) dp[i] = SZ(s[j]);
        }
        else dp[i] = -1;
    }

    // add the root nodes to the answer
    cout << solve((1<<n)-1) + 1;
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 226 ms 1016 KB Output is correct
5 Correct 224 ms 1016 KB Output is correct
6 Correct 225 ms 1528 KB Output is correct
7 Correct 226 ms 1784 KB Output is correct
8 Correct 228 ms 1784 KB Output is correct
9 Correct 224 ms 1912 KB Output is correct
10 Correct 224 ms 1912 KB Output is correct