Submission #133434

#	Time	Username	Problem	Language	Result	Execution time	Memory
133434		forelax	Vještica (COCI16_vjestica)	C++14	160 / 160	153 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){
            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 sb=b&-b ; b-sb ; sb=b&(sb-b)){
            int dp1=dp[sb];
            int dp2=dp[b^sb];
            dp[b]=min(dp[b],dp1+dp2-ml-1);
        }
    }
    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 ++){
                     ~~^~~~~~~~~~~

• Subtask 1: 160 / 160