Submission #1286910

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286910		iq500	Vještica (COCI16_vjestica)	C++20	160 / 160	70 ms	7824 KiB

vjestica

//kanser bitmask sorusu <3
//journey - deco*27
#include <bits/stdc++.h>
using namespace std;

int com[(1<<16)][26], ans[1<<16], gh=0;
int cnt[16][26], n;
string str[16];

int lfms_bt(int x){
    int cnt=0;
    while(x){
        cnt++;
        x/=2;
    }
    return cnt-1; //buraya dikkat!
}

int f(int s){
    //cout<<s<<" "<<ans[s]<<" gh\n";
    if(ans[s]!=-1) return ans[s]; //s=0 ve 1 stringi kapsar

    int add=INT_MAX;
    for(int t=(s-1)&s; t!=0; t=(t-1)&s){
        //cout<<s<<" "<<t<<" "<<(s^t)<<" :( \n";
        add=min(add, f(t)+f(s^t));
    }

    int ort=0;
    for(int i=0; i<26; i++){
        ort+=com[s][i];
    }
    //cout<<add<<" "<<ort<<" ? ";
    ans[s]=add-ort;
    //cout<<s<<" "<<ans[s]<<" döndürür\n";
    return ans[s];


}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>n;

    memset(cnt, 0, sizeof(cnt));
    for(int k=0; k<(1<<n); k++) ans[k]=-1;
    ans[0]=0;

    for(int i=0; i<n; i++){
        cin>>str[i];
        for(int j=0; j<str[i].length(); j++){
            cnt[i][str[i][j]-'a']++;
        }
        ans[(1<<i)]=str[i].length();
    }

    for(int i=0; i<26; i++) com[0][i]=37373737;

    for(int k=1; k<(1<<n); k++){ //her set için ortakları bulma
        int x=lfms_bt(k);
        int dec=k^(1<<x);
        for(int i=0; i<26; i++){
            com[k][i]=min(cnt[x][i], com[dec][i]);
        }
    }
    cout<<f((1<<n)-1)+1;



    return 0;
}

• Subtask 1: 160 / 160