oj.uz

Submission #24990

# Submission time Handle Problem Language Result Execution time Memory
24990 2017-06-19T16:33:58 Z samir_droubi Vještica (COCI16_vjestica) C++14
160 / 160
 399 ms 3180 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3044 KB Output is correct
2 Correct 0 ms 3044 KB Output is correct
3 Correct 0 ms 3044 KB Output is correct
4 Correct 353 ms 3044 KB Output is correct
5 Correct 373 ms 3044 KB Output is correct
6 Correct 399 ms 3180 KB Output is correct
7 Correct 379 ms 3180 KB Output is correct
8 Correct 386 ms 3180 KB Output is correct
9 Correct 369 ms 3180 KB Output is correct
10 Correct 379 ms 3180 KB Output is correct