Submission #298984

#	Time	Username	Problem	Language	Result	Execution time	Memory
298984		TadijaSebez	Vještica (COCI16_vjestica)	C++11	160 / 160	104 ms	1144 KiB

vjestica

#include <bits/stdc++.h>
using namespace std;
const int N=16;
const int A=26;
int cnt[N][A],mn[A];
int dp[1<<N];
const int L=1000050;
char s[L];
int main(){
	int n;
	scanf("%i",&n);
	for(int i=0;i<n;i++){
		scanf("%s",s+1);
		int m=strlen(s+1);
		for(int j=1;j<=m;j++){
			cnt[i][s[j]-'a']++;
		}
		dp[1<<i]=m;
	}
	for(int i=0;i<1<<n;i++)if(__builtin_popcount(i)>1){
		dp[i]=1e9;
		for(int j=i;;){
			j=(j-1)&i;
			if(j==0)break;
			dp[i]=min(dp[i],dp[j]+dp[i^j]);
		}
		for(int j=0;j<A;j++)mn[j]=1e9;
		for(int j=0;j<n;j++)if(i>>j&1){
			for(int z=0;z<A;z++)mn[z]=min(mn[z],cnt[j][z]);
		}
		for(int j=0;j<A;j++)dp[i]-=mn[j];
	}
	printf("%i\n",dp[(1<<n)-1]+1);
	return 0;
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  scanf("%i",&n);
      |  ~~~~~^~~~~~~~~
vjestica.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   scanf("%s",s+1);
      |   ~~~~~^~~~~~~~~~

• Subtask 1: 160 / 160