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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include <string>
#include <cassert>
#include <algorithm>
#include <vector>

// Config selector:
// 1 == Debug
// 0 == Release
#if 0

// Debug config
#define ASSERT(expr) assert(expr)
#define DBG(expr) expr

#else

// Release config
#define ASSERT(expr) do {} while (0)
#define DBG(expr) do {} while (0)

#endif

enum DutyType
{
	OFFICE_MEETING = '1',
	REMOTE_MEETING = '2',
	FREE           = '3'
};

int n; // number of segments
int k; // max number of meetings that can be skipped
int t; // time of drive to and from the office

// XXX_meetings_before[i] contains number of meetings before time i
// Note: size is n+1
std::vector<int> office_meetings_before;
std::vector<int> remote_meetings_before;

// begin > end denotes an empty range.
int count_office_meetings(int begin, int end)
{
	return std::max(0,
			office_meetings_before[std::clamp(end, 0, n)] - office_meetings_before[std::clamp(begin, 0, n)]);
}

// begin > end denotes an empty range.
int count_remote_meetings(int begin, int end)
{
	return std::max(0,
			remote_meetings_before[std::clamp(end, 0, n)] - remote_meetings_before[std::clamp(begin, 0, n)]);
}

// begin > end denotes an empty range.
int count_meetings(int begin, int end)
{
	return count_office_meetings(begin, end) + count_remote_meetings(begin, end);
}

// begin > end denotes an empty range.
int range_length(int begin, int end)
{
	return std::max(end - begin, 0);
}

// Arguments denote the time period spent in the office (length is office_end-office_begin).
// Time periods are:
// [0; office_begin - t]            : at home
// [office_begin - t; office_begin] : driving to the office
// [office_begin; office_end]       : in the office
// [office_end; office_end + t]     : driving home
// [office_end + t; n]              : at home
int compute_max_time_for_competition(int office_begin, int office_end)
{
	ASSERT(office_begin <= office_end);

	int const meetings_during_driving = count_meetings(office_begin - t, office_begin)
		+ count_meetings(office_end, office_end + t);

	int const office_meetings_during_home = count_office_meetings(0, office_begin - t)
		+ count_office_meetings(office_end + t, n);

	int const surely_lost_meetings = meetings_during_driving + office_meetings_during_home;
	if (surely_lost_meetings > k)
	{
		return -1; // impossible to skip <= k meetings
	}

	int const remote_meetings_during_home = count_remote_meetings(0, office_begin - t)
		+ count_remote_meetings(office_end + t, n);

	// Taking max because our budget can be larger than number of planned meetings - in this case we ignore them all.
	int const necessary_meetings_at_home = std::max(0,
			// number of planned meetings - how many more Bajtazar can skip
			remote_meetings_during_home - (k - surely_lost_meetings));

	int const total_time_at_home = range_length(0, office_begin - t)
		+ range_length(office_end + t, n);

	ASSERT(necessary_meetings_at_home <= total_time_at_home);
	return total_time_at_home - necessary_meetings_at_home;
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	std::cin >> n >> k >> t;

	std::string duties;
	duties.reserve(n);
	std::cin >> duties;
	ASSERT((int)duties.size() == n);

	office_meetings_before.resize(n + 1);
	ASSERT(office_meetings_before[0] == 0);
	for (int i = 0; i < n; ++i)
	{
		office_meetings_before[i + 1] = office_meetings_before[i] + (duties[i] == OFFICE_MEETING);
	}

	remote_meetings_before.resize(n + 1);
	ASSERT(remote_meetings_before[0] == 0);
	for (int i = 0; i < n; ++i)
	{
		remote_meetings_before[i + 1] = remote_meetings_before[i] + (duties[i] == REMOTE_MEETING);
	}

	// First compute result if Bajtazar does not go to the office.
	int max_time_for_competition = compute_max_time_for_competition(n + t, n + t);
	// Then consider all possible periods of time spent in the office, making sure that Bajtazar is at home
	// at time 0 and at time n.
	for (int office_begin = t; office_begin + t <= n; ++office_begin)
	{
		for (int office_end = office_begin; office_end + t <= n; ++office_end)
		{
			max_time_for_competition = std::max(max_time_for_competition,
					compute_max_time_for_competition(office_begin, office_end));
		}
	}

	std::cout << max_time_for_competition << '\n';
}