Submission #133428

#	Time	Username	Problem	Language	Result	Execution time	Memory
133428		forelax	Vještica (COCI16_vjestica)	C++14	128 / 160	90 ms	1144 KiB

vjestica

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> gl(n);
    vector<vector<int> > v(n,vector<int> (26));
    for(int i = 0 ; i < n ; i ++){
        string g;
        cin>>g;
        gl[i]=g.length();
        for(int j = 0 ; j < g.length() ; j ++)
            v[i][g[j]-'a']++;
    }
    vector<int> dp(1<<n);
    dp[0]=1;
    for(int b = 1 ; b < dp.size() ; b ++){
        vector<int> g;
        vector<int> minTable(26,1e9);
        for(int i = 0 ; i < n ; i ++)
            if(b&(1<<i)){
                g.push_back(i);
                for(int j = 0 ; j < 26 ; j ++)
                    minTable[j]=min(minTable[j],v[i][j]);
            }
        if(g.size()==1){
//            cout<<dp[b-1]<<endl;
            dp[b]=gl[g[0]]+1;
            continue;
        }
        int ml=0;
        for(int i = 0 ; i < 26 ; i ++)
            ml+=minTable[i];
        dp[b]=1e9;
        for(int i = 0 ; i < 26 ; i ++){
            int f=0,s=0;
            for(int j = 0 ; j < g.size() ; j ++){
                if(v[g[j]][i]==minTable[i])
                    f+=(1<<g[j]);
                else
                    s+=(1<<g[j]);
            }
            if(f==0||s==0)continue;
//            cout<<b<<" "<<i<<" "<<f<<" "<<s<<endl;
            dp[b]=min(dp[b],dp[f]+dp[s]-ml-1);
        }
        if(dp[b]==1e9)
            dp[b]=ml+1;
//        cout<<dp[b-1]<<endl;
    }
    cout<<dp[-1+(1<<n)];
}



/***

2
a
ab
abc

**/

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:12:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < g.length() ; j ++)
                         ~~^~~~~~~~~~~~
vjestica.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 1 ; b < dp.size() ; b ++){
                     ~~^~~~~~~~~~~
vjestica.cpp:37:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0 ; j < g.size() ; j ++){
                             ~~^~~~~~~~~~

• Subtask 1: 128 / 160