Submission #298988

#	Time	Username	Problem	Language	Result	Execution time	Memory
298988		MladenP	Vještica (COCI16_vjestica)	C++17	160 / 160	195 ms	1400 KiB

vjestica

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define lld long long
#define pll pair<lld,lld>
#define all(x) begin(x),end(x)
#define mid ((l+r)/2)
#define sz(x) int((x).size())
#define endl '\n'
#define PRINT(x) cerr<<#x<<'='<<x<<endl
#define INF 1000000000
#define pb push_back
using namespace std;
#define MAXN 20
int cnt[MAXN][30];
int dp[2000000], N, L[2000000];
int len(int mask) {
    if(L[mask] > 0) return L[mask];
    int c[30];
    for(int i = 0; i < 26; i++) c[i] = INF;
    for(int i = 0; i < N; i++) {
        if((1<<i)&mask) {
            for(int j = 0; j < 26; j++) c[j] = min(c[j], cnt[i][j]);
        }
    }
    for(int i = 0; i < 26; i++) L[mask] += c[i];
    return L[mask];
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++) {
        string x; cin >> x;
        for(auto s : x) {
            cnt[i][s-'a']++;
        }
    }

    for(int mask = 1; mask < (1<<N); mask++) {
        if(__builtin_popcount(mask) == 1) {
            dp[mask] = len(mask);
            continue;
        }
        dp[mask] = INF;
        int submask = mask;
        submask = (submask-1)&mask;
        while(submask > 0) {
            dp[mask] = min(dp[mask], dp[submask]+dp[submask^mask]-len(mask));
            submask = (submask-1)&mask;
        }
    }
    int kraj = 0;
    for(int i = 0; i < N; i++) kraj |= (1<<i);
    cout << dp[kraj] +1;
    return 0;
}

• Subtask 1: 160 / 160