oj.uz

Submission #299008

# Submission time Handle Problem Language Result Execution time Memory
299008 2020-09-14T12:08:34 Z jovan_b Vještica (COCI16_vjestica) C++17
160 / 160
 184 ms 1912 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll cnt[25][26];
ll dp[1000005];
ll cc[26];

const int INF = 1000000009;

string s[20];

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    for(int i=1; i<(1<<n); i++) dp[i] = INF;
    for(int i=1; i<=n; i++){
        cin >> s[i];
        for(auto c : s[i]){
            cnt[i][c-'a']++;
        }
        dp[(1<<(i-1))] = s[i].size();
    }
    for(int mask=1; mask<(1<<n); mask++){
        int mxpref = 0;
        for(int i=0; i<26; i++) cc[i] = INF;
        for(int i=1; i<=n; i++){
            if((1<<(i-1)) & mask){
                for(int j=0; j<26; j++) cc[j] = min(cc[j], cnt[i][j]);
            }
        }
        for(int i=0; i<26; i++) mxpref += cc[i];
        for(int j=mask; j; j=(j-1)&mask){
            if(j == mask) continue;
            dp[mask] = min(dp[mask], -mxpref + dp[j] + dp[j^mask]);
        }
    }
    cout << dp[(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 1 ms 384 KB Output is correct
4 Correct 182 ms 936 KB Output is correct
5 Correct 180 ms 1024 KB Output is correct
6 Correct 181 ms 1408 KB Output is correct
7 Correct 184 ms 1784 KB Output is correct
8 Correct 182 ms 1792 KB Output is correct
9 Correct 183 ms 1792 KB Output is correct
10 Correct 184 ms 1912 KB Output is correct