1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>

struct calendar
{
int l_c1,l_c2,l_t1,l_t2;
int r_c1,r_c2,r_t1,r_t2;
};

int main()
{
char *str;
int n,k,t,i,j,c1,c2,l_st,r_st,l_sp,b_sp,r_sp,r;
struct calendar *C;

	scanf("%d %d %d",&n,&k,&t);
	str = (char*) malloc((n+1)*sizeof(char));
	scanf("%s",str);
	
	c1 = c2 = 0;
	for (i = 0; i < n; i++)
	{
		if (str[i] == '1') c1++;
		if (str[i] == '2') c2++;
	}

/*
	printf("%d %d %d",n,k,t);
	printf("\n%s\n\n",str);
*/
	if (c1 - k <= 0)
	{
		printf("%d\n",n - ((k > c1+c2) ? 0 : c1+c2-k));
	} else
	{
		C = (struct calendar *) malloc(n*sizeof(struct calendar));
		for (i = 0; i < n; i++)
		{			
			C[i].l_t1 = ((i > 0) ? C[i-1].l_t1 : 0) + ((str[i] == '1') ? 1 : 0) - ((i > t) ? ((str[i-t] == '1') ? 1 : 0) : 0);
			C[i].l_t2 = ((i > 0) ? C[i-1].l_t2 : 0) + ((str[i] == '2') ? 1 : 0) - ((i > t) ? ((str[i-t] == '2') ? 1 : 0) : 0);
			C[i].l_c1 += ((i > 0) ? C[i-1].l_c1 : 0) + ((str[i] == '1') ? 1 : 0);
			C[i].l_c2 += ((i > 0) ? C[i-1].l_c2 : 0) + ((str[i] == '2') ? 1 : 0);
		}

		for (i = n-1; i >= 0; i--)
		{			
			C[i].r_t1 = ((i < n-1) ? C[i+1].r_t1 : 0) + ((str[i] == '1') ? 1 : 0) - ((i < n-t) ? ((str[i+t] == '1') ? 1 : 0) : 0);
			C[i].r_t2 = ((i < n-1) ? C[i+1].r_t2 : 0) + ((str[i] == '2') ? 1 : 0) - ((i < n-t) ? ((str[i+t] == '2') ? 1 : 0) : 0);
			C[i].r_c1 += ((i < n-1) ? C[i+1].r_c1 : 0) + ((str[i] == '1') ? 1 : 0);
			C[i].r_c2 += ((i < n-1) ? C[i+1].r_c2 : 0) + ((str[i] == '2') ? 1 : 0);			
		}
//		for (i = 0; i < n; i++)
//			printf("debug n = %d:\tc1 = %d, c2 = %d, t1 = %d t2 = %d\tc1 = %d, c2 = %d, t1 = %d, t2 = %d\n",i+1,C[i].l_c1,C[i].l_c2,C[i].l_t1,C[i].l_t2,C[i].r_c1,C[i].r_c2,C[i].r_t1,C[i].r_t2);

		r = -1;
		for (i = t; i < n-t; i++)
		{
			for (j = i+1; j < n-t+1; j++)
			{
				l_st = C[i-1].l_c1 + C[i-1].l_t2;
				r_st = C[j].r_c1 + C[j].r_t2;
				l_sp = C[i-1].l_c2 - C[i-1].l_t2;
				b_sp = c1 - C[i-1].l_c1 - C[j].r_c1 + c2 - C[i-1].l_c2 - C[j].r_c2;
				r_sp = C[j].r_c2 - C[j].r_t2;

//				printf("debug (%d,%d) - (%d,%d):\t%d + %d\tl_s(%d) = %d, b_s(%d) = %d, r_s(%d) = %d\tr = %d\t",i-2+1,i-1+1,j+1,j+2,l_st,r_st,i-t,l_sp,j-i,b_sp,n-j-t,r_sp,r);
				if (k < l_st + r_st) ; //printf("-1\n"); 
				else 
				{
					if (r < n - 2*t - j + i - l_sp - r_sp + k - l_st - r_st) r = n - 2*t - j + i - l_sp - r_sp + k - l_st - r_st;
//					printf("%d-2*%d-%d+%d-%d-%d+%d-%d-%d=%d %d\n",n,t,j,i,l_sp,r_sp,k,l_st,r_st,r,n - 2*t - j + i - l_sp - r_sp + k - l_st - r_st);
				}
			}
		}
		printf("%d\n",r);

		free(C);
	}

	free(str);
	
	return 0;
}