oj.uz

Submission #92602

# Submission time Handle Problem Language Result Execution time Memory
92602 2019-01-04T01:41:07 Z luciocf Vještica (COCI16_vjestica) C++14
160 / 160
 545 ms 2244 KB 
#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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 956 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 529 ms 1188 KB Output is correct
5 Correct 531 ms 1272 KB Output is correct
6 Correct 534 ms 1784 KB Output is correct
7 Correct 537 ms 1912 KB Output is correct
8 Correct 545 ms 2244 KB Output is correct
9 Correct 539 ms 2040 KB Output is correct
10 Correct 542 ms 2168 KB Output is correct