Submission #542223

#	Time	Username	Problem	Language	Result	Execution time	Memory
542223		__Variatto	Vještica (COCI16_vjestica)	C++17	160 / 160	1296 ms	1252 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=7e4+10, A=30, N=20, MAXV=1e6+10;
int n, dp[MAX], mini[A], roz[N];
int ile[N][A];
string s;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>s;
        roz[i]=s.size();
        for(int j=0; j<s.size(); j++)
            ile[i][s[j]-'a']++;
    }
    for(int i=1; i<(1<<n); i++){
        int x=i, l=1;
        bool pierw=true;
        vector<int>zap;
        while(x){
            if(x%2){
                if(pierw){
                    for(int j=0; j<='z'-'a'; j++)
                        mini[j]=ile[l][j];
                    pierw=false;
                }
                for(int j=0; j<='z'-'a'; j++)
                    mini[j]=min(mini[j], ile[l][j]);
                zap.pb(l);
            }
            x/=2, l++;
        }
        dp[i]=MAXV;
        if(__builtin_popcount(i)==1){
            dp[i]=roz[zap[0]];
            continue;
        }
        int maxi=0;
        for(int j=0; j<='z'-'a'; j++)
            maxi+=mini[j];
        for(int j=1; j<(1<<int(zap.size()))-1; j++){
            int l1=0, x1=j;
            int maska=0;
            while(x1){
                if(x1%2) maska+=(1<<(zap[l1]-1));
                x1/=2, l1++;
            }
            dp[i]=min(dp[i], dp[maska]+dp[i^maska]-maxi);
            //cout<<i<<" "<<maska<<" "<<(i^maska)<<"   "<<dp[maska]<<" "<<dp[i^maska]<<" "<<maxi<<"\n";
        }
    }
    cout<<dp[(1<<n)-1]+1<<"\n";
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int j=0; j<s.size(); j++)
      |                      ~^~~~~~~~~

• Subtask 1: 160 / 160