Submission #816947

#	Time	Username	Problem	Language	Result	Execution time	Memory
816947		Theo830	Vještica (COCI16_vjestica)	C++17	160 / 160	150 ms	1888 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i = a;i < b;i++)
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define pb push_back
#define F first
#define S second
const ll INF = 1e9+7;
ll dp[1<<16];
ll exo[1<<16];
ll siz[16][26];
ll n;
ll koina(ll mask){
    if(exo[mask] != -1){
        return exo[mask];
    }
    ll mini[26];
    f(j,0,26){
        mini[j] = INF;
    }
    f(i,0,n){
        if((mask & (1<<i))){
            f(j,0,26){
                mini[j] = min(mini[j],siz[i][j]);
            }
        }
    }
    ll ans = 0;
    f(j,0,26){
        ans += mini[j];
    }
    return exo[mask] = ans;
}
ll solve(ll mask){
    if(dp[mask] != -1){
        return dp[mask];
    }
    ll res = INF;
    bool ok = 0;
    for(ll j = (mask - 1) & mask;j > 0;j = (j - 1) & mask){
        ok = 1;
        res = min(res,solve(j) + solve(mask ^ j) + koina(j) + koina(mask ^ j));
    }
    if(!ok){
        res = 0;
    }
    else{
        res -= 2 * koina(mask);
    }
    return dp[mask] = res;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof dp);
    memset(exo,-1,sizeof exo);
    cin>>n;
    f(i,0,n){
        string s;
        cin>>s;
        f(j,0,26){
            siz[i][j] = 0;
        }
        for(auto x:s){
            siz[i][x - 'a']++;
        }
    }
    cout<<1 + solve((1<<n) - 1) + koina((1<<n) - 1)<<"\n";
}

• Subtask 1: 160 / 160