oj.uz

Submission #453790

# Submission time Handle Problem Language Result Execution time Memory
453790 2021-08-04T21:22:14 Z JovanB Vještica (COCI16_vjestica) C++17
160 / 160
 190 ms 1480 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 16;

int ima[N][26];
int lcp[(1<<N)];
int ch[26];
int dp[(1<<N)];

const int INF = 1000000000;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=0; i<n; i++){
        string s;
        cin >> s;
        for(auto c : s) ima[i][c - 'a']++;
    }
    for(int mask=1; mask<(1<<n); mask++){
        for(int j=0; j<26; j++) ch[j] = INF;
        lcp[mask] = 1;
        for(int i=0; i<n; i++){
            if((1 << i) & mask){
                for(int j=0; j<26; j++) ch[j] = min(ch[j], ima[i][j]);
            }
        }
        for(int j=0; j<26; j++) lcp[mask] += ch[j];
    }
    for(int mask=1; mask<(1<<n); mask++){
        dp[mask] = INF;
        if(__builtin_popcount(mask) == 1){
            dp[mask] = lcp[mask];
            continue;
        }
        for(int submask=mask; submask; submask=(submask-1)&mask){
            if(submask == mask) continue;
            int ost = mask ^ submask;
            dp[mask] = min(dp[mask], dp[submask] + dp[ost] - lcp[mask]);
        }
    }
    cout << dp[(1 << n) - 1] << "\n";
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 182 ms 764 KB Output is correct
5 Correct 183 ms 904 KB Output is correct
6 Correct 183 ms 1120 KB Output is correct
7 Correct 185 ms 1296 KB Output is correct
8 Correct 186 ms 1480 KB Output is correct
9 Correct 184 ms 1304 KB Output is correct
10 Correct 190 ms 1300 KB Output is correct