oj.uz

답안 #439815

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439815 2021-06-30T20:57:55 Z rainboy Vještica (COCI16_vjestica) C
160 / 160
 157 ms 1220 KB 
#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

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.0 / 160.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 131 ms 896 KB Output is correct
5 Correct 127 ms 804 KB Output is correct
6 Correct 127 ms 1036 KB Output is correct
7 Correct 134 ms 1160 KB Output is correct
8 Correct 157 ms 1204 KB Output is correct
9 Correct 129 ms 1220 KB Output is correct
10 Correct 129 ms 1208 KB Output is correct