Submission #712002

#	Time	Username	Problem	Language	Result	Execution time	Memory
712002		Doncho_Bonboncho	Vještica (COCI16_vjestica)	C++14	160 / 160	98 ms	5352 KiB

vjestica

#include <algorithm>
#include <bits/stdc++.h>
#include <cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 20;
const int ALF = 26;
const int INF = 1e9;
const int mod = 1e9 + 7;

int num[MAX_N][ALF];
std::string str[MAX_N];

int dp[1<<MAX_N];


int calcPref( int mask ){

	int currNum[ALF];
	std::fill( currNum, currNum + ALF , INF );

	for( int i=0 ; i<MAX_N ; i++ ){
		if( mask & (1<<i) ){
			for( int j=0 ; j<ALF ; j++ ){
				currNum[j] = std::min( currNum[j], num[i][j] );
			}
		}
	}
	ll nas = 0;
	for( int i=0 ; i<ALF ; i++ ) nas += currNum[i];
	return nas;
}

int sol( int mask ){
	//int &ret = dp[mask];
	if( dp[mask] != -1 ) return dp[mask];
	int pref = calcPref( mask );
	if( (mask&-mask) == mask ) return dp[mask] = pref;
	int currNas = INF;
	for( int i = (mask-1)&mask ; i > 0 ; i = (i-1)&mask ){
		currNas = std::min( currNas, sol(i) + sol( mask ^ i ) - pref );
	}
	return dp[mask] = currNas;
}

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	int n;
	std::cin>>n;
	for( int i=0 ; i<n ; i++ ){
		std::cin>>str[i];
		for( int j=0 ; j<str[i].size() ; j++ )
			num[i][str[i][j]-'a'] ++;
	}


	std::memset(dp, -1, sizeof(dp));
	
	std::cout<<sol( (1<<n)-1 )+1<<"\n";

	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 160 / 160