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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <array>
#include <iostream>
#include <numeric>
#include <fstream>
#include <sstream>
#include <optional>
#include <string>

int const DOM = 0;
int const DOM1_SPOTBIUR = 0;
int const DOM2_SPOTZDAL = 1;
int const DOM3_WOLNE = 2;
int const JAZDA = 3;
int const JAZDA1_SPOTBIUR = 3;
int const JAZDA2_SPOTZDAL = 4;
int const JAZDA3_WOLNE = 5;
int const PRACA = 6;
int const PRACA1_SPOTBIUR = 6;
int const PRACA2_SPOTZDAL = 7;
int const PRACA3_WOLNE = 8;
using zliczenia_t = std::array<int, 9>;

std::string to_string(zliczenia_t const& zl) {
	std::ostringstream oss;
	oss << "D[" << zl[0] << " " << zl[1] << " " << zl[2] << "] "
		<< "J[" << zl[3] << " " << zl[4] << " " << zl[5] << "] "
		<< "P[" << zl[6] << " " << zl[7] << " " << zl[8] << "]";

	return oss.str();
}

struct Zadanie {
	int l_segm;
	int l_bimbow;
	int t_dojazdu;
	std::string obowiazki;
};

std::istream& operator>> (std::istream& is, Zadanie& zad) {
	is >> zad.l_segm;
	is >> zad.l_bimbow;
	is >> zad.t_dojazdu;

	is >> zad.obowiazki;

	return is;
}

struct Dojazd {
	int do_pracy;
	int z_pracy;
};

Dojazd pierwszy_dojazd(Zadanie const& zad) {
	return Dojazd{0, zad.t_dojazdu};
};

std::optional< Dojazd > nastepny_dojazd(Dojazd const& d, Zadanie const& zad) {
	if (d.z_pracy + zad.t_dojazdu < zad.obowiazki.size()) {
		return Dojazd{d.do_pracy, d.z_pracy + 1};
	}

	if (d.do_pracy + 2 * zad.t_dojazdu < zad.obowiazki.size()) {
		return Dojazd{d.do_pracy + 1, d.do_pracy + 1 + zad.t_dojazdu};
	}

	return std::nullopt;
};

enum class Gdzie { dom, dojazd, praca };
int to_int(Gdzie g) {
	return static_cast< int >(g);
};

zliczenia_t sumuj(Zadanie const& zad, Dojazd const& dojazd) {
	enum class CoRobie { rano_dom, dojazd_do_pracy, praca, powrot_z_pracy, wieczor_dom };

	zliczenia_t zlicz{};

	CoRobie cr = CoRobie::rano_dom;
	Gdzie g = Gdzie::dom;

	for (int i = 0; i < zad.obowiazki.size(); ++i) {
		if (i == dojazd.do_pracy) {
			cr = CoRobie::dojazd_do_pracy;
			g = Gdzie::dojazd;
		}
		else if (i == dojazd.z_pracy) {
			cr = CoRobie::powrot_z_pracy;
			g = Gdzie::dojazd;
		}
		else if (i == dojazd.do_pracy + zad.t_dojazdu) {
			cr = CoRobie::praca;
			g = Gdzie::praca;
		}
		else if (i == dojazd.z_pracy + zad.t_dojazdu) {
			cr = CoRobie::wieczor_dom;
			g = Gdzie::dom;
		}

		int poz = 3 * to_int(g) + zad.obowiazki[i] - '1';
		zlicz[poz] += 1;
	}

	return zlicz;
}

struct Przesuw {
	int powrot_koniec_odjechal;
	int powrot_koniec_najechal;

	Przesuw(Zadanie const& zad, Dojazd const& dojazd) {

		powrot_koniec_odjechal = zad.obowiazki[dojazd.z_pracy - 1] - '1';
		powrot_koniec_najechal = zad.obowiazki[dojazd.z_pracy + zad.t_dojazdu - 1] - '1';
	};
};

zliczenia_t deltuj(zliczenia_t const& poprzednie_zliczenia, Przesuw const& przesuw) {
	zliczenia_t zliczenia = poprzednie_zliczenia;

	// wyjezdzam pozniej - co bylo dojazdem staje sie praca
	zliczenia[JAZDA + przesuw.powrot_koniec_odjechal] -= 1;
	zliczenia[PRACA + przesuw.powrot_koniec_odjechal] += 1;

	// wracam pozniej - co bylo domem, staje sie dojazdem
	zliczenia[DOM   + przesuw.powrot_koniec_najechal] -= 1;
	zliczenia[JAZDA + przesuw.powrot_koniec_najechal] += 1;

	return zliczenia;
}

int opuszczone_w_dojezdzie(zliczenia_t const& zliczenia) {
	return zliczenia[JAZDA1_SPOTBIUR] + zliczenia[JAZDA2_SPOTZDAL];
}

int opuszczone_spotkania(zliczenia_t const& zliczenia) {
	return zliczenia[DOM1_SPOTBIUR] + opuszczone_w_dojezdzie(zliczenia);
}

int potyczkuj(zliczenia_t const& zliczenia, int l_bimbow) {
	int opuszczone = opuszczone_spotkania(zliczenia);

	if (l_bimbow < opuszczone_spotkania(zliczenia)) return -1;

	int bimby_do_wykorzystania = l_bimbow - opuszczone_w_dojezdzie(zliczenia);

	return zliczenia[DOM3_WOLNE] + std::min(bimby_do_wykorzystania, zliczenia[DOM1_SPOTBIUR] + zliczenia[DOM2_SPOTZDAL]);
}

int nie_jedzie(Zadanie const& zad) {
	int min_inf = std::numeric_limits< int >::min();
	zliczenia_t zlicz = sumuj(zad, Dojazd{min_inf, min_inf});
	return potyczkuj(zlicz, zad.l_bimbow);
}

int jedzie(Zadanie const& zad) {
	int wynik = -1;

	std::optional< Dojazd > dojazd = std::optional< Dojazd >(pierwszy_dojazd(zad));

	int poprzedni_wyjazd_do_pracy = dojazd->do_pracy - 1;
	zliczenia_t poprzednie_zliczenia {};

	while (dojazd) {
		zliczenia_t zl = dojazd->do_pracy == poprzedni_wyjazd_do_pracy
			? deltuj(poprzednie_zliczenia, Przesuw(zad, dojazd.value()))
			: sumuj(zad, dojazd.value());

		int w = potyczkuj(zl, zad.l_bimbow);
		wynik = std::max(wynik, w);

		poprzedni_wyjazd_do_pracy = dojazd->do_pracy;
		poprzednie_zliczenia = zl;

		dojazd = nastepny_dojazd(dojazd.value(), zad);
	}

	return wynik;
}

int main() {
	Zadanie zad;
	std::cin >> zad;

	int wynik = nie_jedzie(zad);
	if (wynik == -1) wynik = jedzie(zad);

	std::cout << wynik << "\n";
}