Submission #225785

#	Time	Username	Problem	Language	Result	Execution time	Memory
225785		osaaateiasavtnl	Vještica (COCI16_vjestica)	C++14	160 / 160	117 ms	1916 KiB

vjestica

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 17, INF = 1e9 + 7;
int dp[1 << N];
string a[N];
int cnt[N][26];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    /*
    for (int s=m; s; s=(s-1)&m)
    */
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        for (char c : a[i])
            ++cnt[i][c - 'a'];
    }
    for (int mask = 1; mask < (1 << n); ++mask) {
        int lcp = 0;
        for (int c = 0; c < 26; ++c) {
            int add = INF;
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    add = min(add, cnt[i][c]);
                }   
            }   
            lcp += add;
        }   

        if (bp(mask) == 1) {
            for (int i = 0; i < n; ++i) {
                if ((mask >> i) & 1) {
                    dp[mask] = a[i].size();
                    break;
                }   
            }   
        }   
        else {
            dp[mask] = INF;
            for (int s=mask; s; s=(s-1)&mask) {
                //cout << mask << ' ' << s << ' ' << lcp << endl;
                dp[mask] = min(dp[mask], dp[s] + dp[mask ^ s] - lcp);
            }
        }      
    }   
    int all = (1 << n) - 1;
    cout << dp[all] + 1 << endl;
}

• Subtask 1: 160 / 160