Submission #24990

#	Time	Username	Problem	Language	Result	Execution time	Memory
24990		samir_droubi	Vještica (COCI16_vjestica)	C++14	160 / 160	399 ms	3180 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
int n;
int a[17][26];
int s[17];
const int mxn=(1<<17);
int dp[mxn];
int com[mxn];
int calc(int mask)
{
	if(dp[mask]!=-1)return dp[mask];
	if(mask==0)return 0;
	if(__builtin_popcount(mask)==1)
	{
		int i=0;
		for(i;i<n;++i)
			if((1<<i)&mask)break;
		return s[i];
	}

	for(int j=0;j<26;++j)
	{
		int x=(1e9);
		for(int i=0;i<n;++i)
			if((1<<i)&mask)
				x=min(a[i][j],x);

		com[mask]+=x;
	}


	int ans=(1e9);

	for(int i=(mask-1)&mask;i>0;i=(i-1)&mask)
		ans=min(ans,calc(i)+calc(mask^i)-com[mask]);

	return dp[mask]=ans;
}
int main()
{
	memset(dp,-1,sizeof dp);
	scanf("%d",&n);
	for(int i=0;i<n;++i)
	{
		string t;
		cin>>t;
		s[i]=t.length();
		for(int j=0;j<t.length();++j)
			++a[i][t[j]-'a'];
	}
	printf("%d\n",calc((1<<n)-1)+1);
	return 0;
}

Compilation message (stderr)

vjestica.cpp: In function 'int calc(int)':
vjestica.cpp:16:8: warning: statement has no effect [-Wunused-value]
   for(i;i<n;++i)
        ^
vjestica.cpp: In function 'int main()':
vjestica.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<t.length();++j)
                ^
vjestica.cpp:42:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^

• Subtask 1: 160 / 160