oj.uz

Submission #114806

# Submission time Handle Problem Language Result Execution time Memory
114806 2019-06-03T03:29:35 Z zoooma13 Vještica (COCI16_vjestica) C++14
160 / 160
 387 ms 1692 KB 
#include <bits/stdc++.h>
using namespace std;

int popcount[1<<16] ,lg2[1<<16];

int n;
string s;
vector <int> ch_cnt[16];

int dp[1<<16];
int solve(int bts){
    if(popcount[bts] == 1){
        int idx = lg2[bts&-bts] ,ret = 0;
        for(int c=0; c<26; c++)
            ret += ch_cnt[idx][c];
        return ret;
    }
    if(~dp[bts])
        return dp[bts];

    vector <int> mi(26 ,INT_MAX);
    for(int b=bts; b; b-=(b&-b)){
        int idx = lg2[b&-b];
        for(int c=0; c<26; c++)
            mi[c] = min(mi[c] ,ch_cnt[idx][c]);
    }
    int all_mi = 0;
    for(int c=0; c<26; c++)
        all_mi += mi[c];

    int ans = INT_MAX;
    for(int b=bts; b; b=(b-1)&bts){
        if(b && (bts^b))
            ans = min(ans ,solve(b)+solve(bts^b));
    }

    return dp[bts] = ans-all_mi;
}

int main()
{
    lg2[0] = -1 ,popcount[0] = 0;
    for(int i=1; i<(1<<16); i++){
        lg2[i] = lg2[i-1];
        if((i&(i-1)) == 0)
            lg2[i]++;
        popcount[i] = __builtin_popcount(i);
    }

    cin >> n;
    for(int i=0; i<n; i++){
        ch_cnt[i].resize(26);
        cin >> s;
        for(char c='a'; c<='z'; c++)
            ch_cnt[i][c-'a'] = count(s.begin() ,s.end() ,c);
    }

    memset(dp ,-1 ,sizeof dp);
    cout << solve((1<<n)-1)+1 << endl;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 4 ms 1152 KB Output is correct
4 Correct 364 ms 1144 KB Output is correct
5 Correct 376 ms 1152 KB Output is correct
6 Correct 374 ms 1528 KB Output is correct
7 Correct 374 ms 1580 KB Output is correct
8 Correct 387 ms 1692 KB Output is correct
9 Correct 382 ms 1664 KB Output is correct
10 Correct 374 ms 1668 KB Output is correct