Submission #439815

#	Time	Username	Problem	Language	Result	Execution time	Memory
439815		rainboy	Vještica (COCI16_vjestica)	C11	160 / 160	157 ms	1220 KiB

vjestica

#include <stdio.h>
#include <string.h>

#define N	16
#define A	26
#define L	1000000
#define INF	0x3f3f3f3f

int min(int a, int b) { return a < b ? a : b; }

int main() {
	static char cc[L + 1];
	static int kk[N][A], ll[1 << N], dp[1 << N];
	int n, i, a, b, c;

	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int l, h;

		scanf("%s", cc), l = strlen(cc);
		for (h = 0; h < l; h++)
			kk[i][cc[h] - 'a']++;
	}
	for (b = 1; b < 1 << n; b++)
		for (a = 0; a < A; a++) {
			int k = INF;

			for (i = 0; i < n; i++)
				if ((b & 1 << i) != 0)
					k = min(k, kk[i][a]);
			ll[b] += k;
		}
	for (b = 1; b < 1 << n; b++)
		if ((b & b - 1) == 0)
			dp[b] = ll[b];
		else {
			dp[b] = INF, c = 0;
			while ((c = c - b & b) != b)
				dp[b] = min(dp[b], dp[c] + dp[b ^ c] - ll[b]);
		}
	printf("%d\n", dp[(1 << n) - 1] + 1);
	return 0;
}

Compilation message (stderr)

vjestica.c: In function 'main':
vjestica.c:34:14: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   34 |   if ((b & b - 1) == 0)
      |            ~~^~~
vjestica.c:38:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |    while ((c = c - b & b) != b)
      |                ~~^~~
vjestica.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
vjestica.c:20:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%s", cc), l = strlen(cc);
      |   ^~~~~~~~~~~~~~~

• Subtask 1: 160 / 160