oj.uz

Submission #98348

# Submission time Handle Problem Language Result Execution time Memory
98348 2019-02-22T17:50:54 Z dalgerok Vještica (COCI16_vjestica) C++17
160 / 160
 136 ms 1272 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 16, M = 26;



int n, cnt[N][M], dp[(1 << N)];
string s;


inline int get(int mask){
    int cur[M];
    memset(cur, 63, sizeof(cur));
    for(int i = 0; i < n; i++){
        if((mask >> i) & 1){
            for(int j = 0; j < M; j++){
                cur[j] = min(cur[j], cnt[i][j]);
            }
        }
    }
    int sum = 0;
    for(int i = 0; i < M; i++){
        sum += cur[i];
    }
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    memset(dp, 63, sizeof(dp));
    for(int i = 0; i < n; i++){
        cin >> s;
        for(int j = 0; j < (int)s.size(); j++){
            cnt[i][s[j] - 'a'] += 1;
        }
    }
    for(int i = 1; i < (1 << n); i++){
        int pref = get(i);
        if(__builtin_popcount(i) == 1){
            dp[i] = pref;
        }
        else{
            for(int j = (i - 1) & i; j > 0; j = (j - 1) & i){
                dp[i] = min(dp[i], dp[j] + dp[i ^ j] - pref);
            }
        }
    }
    cout << dp[(1 << n) - 1] + 1;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 90 ms 640 KB Output is correct
5 Correct 136 ms 888 KB Output is correct
6 Correct 103 ms 896 KB Output is correct
7 Correct 122 ms 1152 KB Output is correct
8 Correct 92 ms 1152 KB Output is correct
9 Correct 106 ms 1152 KB Output is correct
10 Correct 99 ms 1272 KB Output is correct