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
#include <iostream>
#include <vector>


int obliczIleZadanMiedzy(std::vector<int> const& iloscZadanWPrefixie, int poczatek, int koniec)
{
  return iloscZadanWPrefixie[koniec] - iloscZadanWPrefixie[poczatek];
}

enum Zadanie {
  Biuro = 1,
  Zdalne = 2,
  Wolne = 3,
};

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

  int n;
  int k;
  int t;
  std::cin >> n >> k >> t;
  int iloscWFinale = 0;
  std::vector<int> zadania;
  for (int i = 0; i < n; ++i)
  {
    char zadanie;
    std::cin >> zadanie;
    if (zadanie == '1')
      zadania.push_back(Zadanie::Biuro);
    if (zadanie == '2')
      zadania.push_back(Zadanie::Zdalne);
    if (zadanie == '3')
      zadania.push_back(Zadanie::Wolne);
  }

  std::vector<int> iloscZadanWPrefixie[4];
  for (int z=1; z<=3; ++z)
  {
    iloscZadanWPrefixie[z].push_back(0);
    for (int i = 0; i < n; ++i)
    {
      if (zadania[i] == z)
        iloscZadanWPrefixie[z].push_back(iloscZadanWPrefixie[z].back() + 1);
      else
        iloscZadanWPrefixie[z].push_back(iloscZadanWPrefixie[z].back());
    }
  }

  int iloscSPotkan = obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], 0, n) +
    obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Zdalne], 0, n);
  
  int minimumSpotkanPotrzebnych = std::max(iloscSPotkan - k, 0);

  int maksWolne = -1;
  if (obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], 0, n) <= k)
  {
    maksWolne = n - minimumSpotkanPotrzebnych;
  }

  for (int wyjazd = 0; wyjazd <= n; ++wyjazd)
  {
    for (int powrot = (wyjazd + 2 * t); powrot <= n; ++powrot)
    {
      int iloscSpotkanWDrodze = obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], wyjazd, wyjazd+t) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], powrot-t, powrot) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Zdalne], wyjazd, wyjazd + t) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Zdalne], powrot - t, powrot);
      if (iloscSpotkanWDrodze + obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], 0, wyjazd) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], powrot, n) > k)
        continue;
      int iloscSPotkanWBiurze = obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Biuro], wyjazd + t, powrot-t) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Zdalne], wyjazd + t, powrot - t);
      int ileSPotkanWDomu = iloscSPotkan - iloscSpotkanWDrodze - iloscSPotkanWBiurze;
      int ileWolnychWDomu = obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Wolne], 0, wyjazd) +
        obliczIleZadanMiedzy(iloscZadanWPrefixie[Zadanie::Wolne], powrot, n);
      
      int ileSpotkanPotrzebnych = std::max(0, minimumSpotkanPotrzebnych - iloscSPotkanWBiurze);
      ileWolnychWDomu += (ileSPotkanWDomu - ileSpotkanPotrzebnych);
      if (maksWolne < ileWolnychWDomu)
        maksWolne = ileWolnychWDomu;
    }
  }
  std::cout << maksWolne << "\n";

  return 0;
}