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
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
using namespace std;
const int OFFICE = 1, REMOTE = 2, FREE = 3;

struct Tasks {
	int office = 0;
	int remote = 0;
	int free = 0;
	void inc(const Tasks &task, const char type) {
		const int t = type - '0';
		office = task.office;
		remote = task.remote;
		free = task.free;
		if (t == OFFICE) {
			office++;
		} else if (t == REMOTE) {
			remote++;
		} else if (t == FREE) {
			free++;
		}
	}
	void print() {
		cout << "[" << office << ", " << remote << ", " << free << "]\n";
	}
};

vector<Tasks> counter;

Tasks calculate(int start, int end) {
	Tasks result;
	if (start > end) {
		return result;
	}
	Tasks &left = counter[start - 1];
	Tasks &right = counter[end];

	result.office = right.office - left.office;
	result.remote = right.remote - left.remote;
	result.free = right.free - left.free;

	return result;
}

int main() {
//	ifstream cin("tests/0a.in");

	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, k, t;
	string s;
	cin >> n;
	cin >> k;
	cin >> t;
	cin >> s;

	counter.resize(n + 1);

	for (int i = 1; i <= n; i++) {
		counter[i].inc(counter[i - 1], s[i - 1]);
	}

	int result = -1;

	Tasks home = calculate(1, n);
	if (home.office <= k) {
		result = home.free + min(k, home.remote + home.office);
	}

	for (int left = 1; left <= n - 2 * t; left++) {
		for (int right = left + t + 1; right <= n - t + 1; right++) {

			Tasks home1 = calculate(1, left - 1);
			Tasks travel1 = calculate(left, left + t - 1);

			Tasks travel2 = calculate(right, right + t - 1);
			Tasks home2 = calculate(right + t, n);

			const int lostOfficeAtHome = home1.office + home2.office;
			const int lostAtTravel = travel1.office + travel1.remote
					+ travel2.office + travel2.remote;
			const int workAtHome = home1.remote + home2.remote;
			const int coding = home1.free + home2.free;

			if (lostOfficeAtHome + lostAtTravel > k) {
				continue;
			}
			int resultCandidate = coding
					+ min(k - lostAtTravel, workAtHome + lostOfficeAtHome);

			if (resultCandidate >= result) {
				result = resultCandidate;
			}
		}
	}

	cout << result << endl;
	return 0;
}