Submission #92602

#	Time	Username	Problem	Language	Result	Execution time	Memory
92602		luciocf	Vještica (COCI16_vjestica)	C++14	160 / 160	545 ms	2244 KiB

vjestica

#include <bits/stdc++.h>

using namespace std;

const int maxn = 17;

const int inf = 1e9+10;

int dp[1<<maxn], qtd[1<<maxn], n;

int mark[maxn][27], menor[27];

string s[maxn];

void calc(void)
{
	for (int mask = 0; mask < (1<<n); mask++)
	{
		for (int i = 0; i < 26; i++)
			menor[i] = inf;

		for (int i = 0; i < n; i++)
			if (mask&(1<<i))
				for (int j = 0; j < 26; j++)
					menor[j] = min(menor[j], mark[i][j]);

		for (int i = 0; i < 26; i++)
			qtd[mask] += menor[i];
	}
}

int solve(int mask)
{	
	if (__builtin_popcount(mask) == 1)
	{
		for (int i = 0; i < n; i++)
			if (mask&(1<<i)) return s[i].size();
	}
	if (dp[mask] != -1) return dp[mask];

	int ans = inf;
	for (int aux = mask; aux > 0; aux = (aux-1)&mask)
	{
		if (aux == mask) continue;

		ans = min(ans, solve(aux)+solve(mask^aux));
	}

	return dp[mask] = ans-qtd[mask];
}

int main(void)
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> s[i];

		for (auto c: s[i])
			mark[i][c-'a']++;
	}

	calc();

	memset(dp, -1, sizeof dp);

	cout << 1+solve((1<<n)-1) << "\n";
}

• Subtask 1: 160 / 160