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
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#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,auto x)->decltype(x.end(),o);
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<")";}
auto&operator<<(auto&o,tuple<auto,auto,auto,auto>t){return o<<"("<<get<0>(t)<<", "<<get<1>(t)<<", "<<get<2>(t)<<", "<<get<3>(t)<<")";}
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

const char meeting_at_office = '1';
const char remote_meeting = '2';
const char no_duties = '3';

using Info = tuple<int, int, int>; // {forced_missed, competition, ambiguous}
Info operator+(Info a, Info b) {
	auto [ax, ay, az] = a;
	auto [bx, by, bz] = b;
	return {ax + bx, ay + by, az + bz};
}
Info operator-(Info a, Info b) {
	auto [ax, ay, az] = a;
	auto [bx, by, bz] = b;
	return {ax - bx, ay - by, az - bz};
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, k, t;
	cin >> n >> k >> t;
	string schedule;
	cin >> schedule;
	debug(n, k, t, schedule);

	int answer = -1;
	auto eval_info = [&](Info x) {
		auto [f, c, a] = x;
		if (f > k)
			return;
		int can_add = k - f;
		c += min(can_add, a);
		answer = max(answer, c);
	};

	auto get_at_home = [&](int id) -> Info {
		if (schedule[id] == meeting_at_office) {
			return {1, 1, 0};
		}
		if (schedule[id] == remote_meeting) {
			return {0, 0, 1};
		}
		if (schedule[id] == no_duties) {
			return {0, 1, 0};
		}
		assert(false);
	};
	auto get_at_office = [&]([[maybe_unused]] int id) -> Info {
		return {0, 0, 0};
	};
	auto get_traveling = [&](int id) -> Info {
		if (schedule[id] == no_duties) {
			return {0, 0, 0};
		}
		else {
			return {1, 0, 0};
		}
	};
	vector<Info> at_home(n), at_office(n), traveling(n);
	REP(i, n) {
		at_home[i] = get_at_home(i);
		at_office[i] = get_at_office(i);
		traveling[i] = get_traveling(i);
	}
	auto make_prefix = [](vector<Info>& v) {
		REP(i, ssize(v) - 1) {
			v[i + 1] = v[i + 1] + v[i];
		}
	};
	make_prefix(at_home);
	make_prefix(at_office);
	make_prefix(traveling);

	auto sum = [&](const vector<Info>& v, int l, int r) -> Info {
		if (r < l)
			return {0, 0, 0};
		if (l == 0)
			return v[r];
		return v[r] - v[l - 1];
	};

	// all time at home
	eval_info(sum(at_home, 0, n - 1));

	// at office from l to r
	FOR(l, 0, n - 1) {
		const int pref_home = l - t;
		if (pref_home < 0) {
			continue;
		}
		const Info pref =
			sum(at_home, 0, pref_home - 1) +
			sum(traveling, pref_home, l - 1);
		FOR(r, l, n - 1) {
			const int suff_home = n - r - t - 1;
			if (suff_home < 0) {
				continue;
			}
			Info value =
				pref +
				sum(at_office, l, r) +
				sum(traveling, r + 1, n - suff_home - 1) +
				sum(at_home, n - suff_home, n - 1);
			eval_info(value);
		}
	}

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