Submission #133483

#	Time	Username	Problem	Language	Result	Execution time	Memory
133483		tdwn	Vještica (COCI16_vjestica)	C++17	160 / 160	351 ms	1276 KiB

vjestica

#include <bits/stdc++.h>
#define ll long long 
#define pb push_back
#define mp make_pair
using namespace std;
int cnt[30][30], n;
int dp[(1<<16)];
int min_val[30];

int solve(int mask) {
	if(dp[mask] != -1) return dp[mask];

	if(__builtin_popcount(mask) == 1) {
		for(int i=0;i<n;i++) {
			if(mask&(1<<i)) {
				int sum = 0;
				for(int j=0;j<26;j++) {
					sum += cnt[i][j];
				}
				return dp[mask] = sum;
			}
		}
	}

	for(int i=0;i<26;i++) min_val[i] = INT_MAX;
	int intersection = 0;
	for(int i=0;i<n;i++) {
		if(mask & (1<<i)) {
			for(int j=0;j<26;j++)
				min_val[j] = min(min_val[j], cnt[i][j]);
		}
	}

	for(int i=0;i<26;i++) intersection += min_val[i];

	dp[mask] = 10000000;
	int b = 0;
	do {
		dp[mask] = min(dp[mask], solve(b) + solve(mask^b) - intersection);
	} while (b=(b-mask)&mask);
	return dp[mask];
}

int main() {
	cin>>n;
	string str;
	for(int i=0;i<n;i++) {
		cin>>str;
		for(int j=0;j<str.length();j++) {
			cnt[i][int(str[j]-'a')]++;
		}
	}

	memset(dp,-1,sizeof(dp));
	cout<<solve((1<<n)-1) + 1;
}

Compilation message (stderr)

vjestica.cpp: In function 'int solve(int)':
vjestica.cpp:40:12: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  } while (b=(b-mask)&mask);
           ~^~~~~~~~~~~~~~
vjestica.cpp: In function 'int main()':
vjestica.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<str.length();j++) {
               ~^~~~~~~~~~~~~

• Subtask 1: 160 / 160