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
127
128
129
130
#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using ll = long long;

constexpr char OFFICE = '1';
constexpr char REMOTE = '2';
constexpr char NOMEET = '3';
constexpr int MAXN = 8000;
constexpr int INFTY = 2 * MAXN;

int main() {
	std::ios_base::sync_with_stdio(0); std::cin.tie(0);
	
	int n, k, t;
	std::cin >> n >> k >> t;
	
	std::string word;
	std::cin >> word;
	word.insert(word.begin(), '.');
	word.push_back(NOMEET);
	
	std::vector<int> prefsum_meetings(n+1);
	for (int i = 1; i <= n; ++i) {
		prefsum_meetings[i] = prefsum_meetings[i-1] + (word[i] != NOMEET);
	}
	
	k = std::min(k, prefsum_meetings[n]);
	
	// dp[0/1][i][s] -- max number of fun hours in length=i prefix if skipped =s meetings and i-th hour spent at home/work.
	std::array<std::vector<std::vector<int>>, 2> dp {{
		std::vector<std::vector<int>>(n+2, std::vector<int>(k + 1)),
		std::vector<std::vector<int>>(n+2, std::vector<int>(k + 1)),
	}};
	
	// Count the number of meetings of either kind on [p, q]
	auto count_meetings = [&](int p, int q) -> int {
		return prefsum_meetings[q] - prefsum_meetings[p - 1];
	};
	
	for (int i = 1; i <= n+1; ++i) {
		for (int s = 0; s <= k; ++s) {
			
			int departed = i - t;
			bool can_drive = departed >= 1;
			int drive_skipped;
			if (can_drive) {
				drive_skipped = count_meetings(i - t, i - 1);
				can_drive = s >= drive_skipped;
			}
			
			int sofar_if_noskip[2];
			int sofar_if_skip[2];
			
			for (int loc : {0, 1}) {
				sofar_if_noskip[loc] = std::max(can_drive ? dp[loc^1][departed - 1][s - drive_skipped] : -INFTY, dp[loc][i - 1][s]);
				sofar_if_skip[loc] = s > 0 ? std::max(can_drive && s - drive_skipped >= 1 ? dp[loc^1][departed - 1][s - drive_skipped - 1] : -INFTY, dp[loc][i - 1][s - 1]) : -INFTY;
			}
			
			if (word[i] == NOMEET) {
				dp[0][i][s] = sofar_if_noskip[0] + 1;
				dp[1][i][s] = departed >= 1 ? sofar_if_noskip[1] : -INFTY;
			} else if (word[i] == REMOTE) {
				dp[0][i][s] = std::max(sofar_if_noskip[0], sofar_if_skip[0] + 1);
				dp[1][i][s] = departed >= 1 ? std::max(sofar_if_noskip[1], sofar_if_skip[1]) : -INFTY;
			} else if (word[i] == OFFICE) {
				dp[0][i][s] = s > 0 ? sofar_if_skip[0] + 1 : -INFTY;
				dp[1][i][s] = departed >= 1 ? std::max(sofar_if_noskip[1], sofar_if_skip[1]) : -INFTY;
			} else {
				__builtin_unreachable();
			}
		}
	}
	
//	for (int i = 1; i <= n+1; ++i) {
//		std::cout << "dp[0][i="<<i<<"]:";
//		for (int s = 0; s <= k; ++s) {
//			std::cout << ' ' << dp[0][i][s];
//		}
//		std::cout << '\n';
//		std::cout << "dp[1][i="<<i<<"]:";
//		for (int s = 0; s <= k; ++s) {
//			std::cout << ' ' << dp[1][i][s];
//		}
//		std::cout << '\n';
//	}
	
	int answer = -INFTY;
	for (int s = 0; s <= k; ++s) {
		answer = std::max(answer, dp[0][n+1][s] - 1);
	}
	
	if (answer < 0) {
		answer = -1;
	}
	
	std::cout << answer << '\n';
	
	/*
	std::vector<int> prefsum_remote(n+1);
	std::vector<int> prefsum_office(n+1);
	
	for (int i = 1; i <= n; ++i) {
		prefsum_remote[i] = prefsum_remote[i-1] + (word[i -1] == REMOTE);
		prefsum_office[i] = prefsum_office[i-1] + (word[i -1] == OFFICE);
	}
	
	// L[i] -- # of meetings skipped by leaving for work at i
	// R[i] -- # of meetings skipped by leaving work at i
	std::vector<int> L(n+1);
	std::vector<int> R(n+1);
	
	for (int i = 1; i + t - 1 <= n; ++i) {
		L[i] = (
			prefsum_office[i + t - 1]
			+
			prefsum_remote[i + t - 1] - prefsum_remote[i - 1]
		);
		R[i] = (
			prefsum_office[n] - prefsum_office[i - 1]
			+
			prefsum_remote[i + t - 1] - prefsum_remote[i - 1]
		);
	}
	
	std::vector<int> prefmin_L(n+1);
	std::vector<int> sm_R(n+1);
	*/
}