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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
#define ssize(x) int(x.size())
#ifdef DEBUG
auto &operator << (auto &o, pair<auto, auto> p) {
	return o << "(" << p.first << ", " << p.second << ")";
}
auto operator << (auto &o, auto x) -> decltype(x.end(), o) {
	o << "{"; int i = 0;
	for (auto e : x) o << ","+!i++ << e;
	return o << "}";
}
#define debug(X...) cerr << "["#X"]: ", [](auto ...$) {((cerr << $ << "; "), ...) << endl;}(X)
#else
#define debug(...) {}
#endif

enum Duty {
	StationaryMeeting,
	OnlineMeeting,
	Freetime
};

int n, k, t;
vector<Duty> duties;
vector<int> stationary_pref;
vector<int> online_pref;

void preprocessing() {
	stationary_pref = online_pref = vector<int>(n);

	REP (i, n) {
		if (i > 0) {
			online_pref[i] = online_pref[i - 1];
			stationary_pref[i] = stationary_pref[i - 1];
		}

		if (duties[i] == Duty::StationaryMeeting)
			stationary_pref[i]++;
		if (duties[i] == Duty::OnlineMeeting)
			online_pref[i]++;
	}
}

int get_sum(int l, int r, vector<int> &pref) {
	if (l > r) return 0;
	if (l == 0)
		return pref[r];
	return pref[r] - pref[l - 1];
}

int stay_at_home() {
	int online = get_sum(0, n - 1, online_pref);
	int stationary = get_sum(0, n - 1, stationary_pref);
	debug(online, stationary);

	int can_miss = k - stationary;
	if (can_miss < 0) return -1;

	int attended_online = max(0, online - can_miss);

	int home_result = n - attended_online;
	debug(home_result);
	return home_result;
}

int solve(int work_start, int work_end) {
	debug(work_start, work_end);
	int missed_online =
		get_sum(work_start - t, work_start - 1, online_pref) +
		get_sum(work_end + 1, work_end + t, online_pref);

	int missed_stationary = 
		get_sum(0, work_start - 1, stationary_pref) +
		get_sum(work_end + 1, n - 1, stationary_pref);

	debug(missed_online, missed_stationary);

	int total_missed = missed_online + missed_stationary;
	int can_miss = k - total_missed;
	if (can_miss < 0) return -1;

	int left_online = 
		get_sum(0, work_start - t - 1, online_pref) +
		get_sum(work_end + t + 1, n - 1, online_pref);

	int attended_online = max(0, left_online - can_miss);
	int time_in_work = work_end - work_start + 1 + 2 * t;
	int result = n - time_in_work - attended_online;
	debug(result);
	return result;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> k >> t;

	duties.resize(n);
	string duties_str;
	cin >> duties_str;
	REP (i, n)
		duties[i] = Duty(duties_str[i] - '0' - 1);

	preprocessing();

	int answer = stay_at_home();
	FOR (l, t, n - t - 1) {
		FOR (r, l, n - t - 1) {
			answer = max(answer, solve(l, r));
		}
	}

	cout << answer << '\n';
}