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
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, skippable_cnt, travel_time;
    int i, j, res;
    cin >> n >> skippable_cnt >> travel_time;
    
    string tasks;
    cin >> tasks;
    
    int in_person_meetings = 0;
    for (i = 0; i < n; ++i)
    {
        in_person_meetings += tasks[i] == '1';
    }
    
    // No need to travel to office.
    if (skippable_cnt >= in_person_meetings)
    {
        res = 0;
        int skippable_remotes_cnt = skippable_cnt - in_person_meetings;
        
        for (i = 0; i < n; ++i)
        {
            if (tasks[i] == '1' || tasks[i] == '3')
            {
                ++res;
            }
            else
            {
                if (skippable_remotes_cnt > 0)
                {
                    ++res;
                    --skippable_remotes_cnt;
                }
            }
        }
        
        cout << res << "\n";
        return 0;
    }
    
    vector<int> skipped_during_travel(n);
    int skipped = 0;
    for (i = 0; i < travel_time; ++i)
    {
        skipped += (tasks[i] == '1') || (tasks[i] == '2');
    }
    skipped_during_travel[0] = skipped;
    for (i = 1; i < n - travel_time + 1; ++i)
    {
        skipped = skipped_during_travel[i - 1];
        
        skipped -= (tasks[i - 1] == '1') || (tasks[i - 1] == '2');
        skipped += (tasks[i + travel_time - 1] == '1') || (tasks[i + travel_time - 1] == '2');
        
        skipped_during_travel[i] = skipped;
    }
    
    vector<int> in_person_meetings_before(n);
    in_person_meetings_before[0] = 0;
    for (i = 1; i < n; ++i)
    {
        in_person_meetings_before[i] = in_person_meetings_before[i - 1] + (tasks[i - 1] == '1');
    }
    
    vector<int> in_person_meetings_after(n);
    in_person_meetings_after[n - 1] = 0;
    for (i = n - 2; i >= 0; --i)
    {
        in_person_meetings_after[i] = in_person_meetings_after[i + 1] + (tasks[i + 1] == '1');
    }
    
    vector<int> no_tasks_before(n);
    no_tasks_before[0] = 0;
    for (i = 1; i < n; ++i)
    {
        no_tasks_before[i] = no_tasks_before[i - 1] + (tasks[i - 1] == '3');
    }
    vector<int> no_tasks_after(n);
    no_tasks_after[n - 1] = 0;
    for (i = n - 2; i >= 0; --i)
    {
        no_tasks_after[i] = no_tasks_after[i + 1] + (tasks[i + 1] == '3');
    }
    
    res = -1;
    for (i = 0; i < n - 2 * travel_time; ++i)
    {
        for (j = i + travel_time + 1; j < n - travel_time + 1; ++j)
        {
            int skipped_on_travel = skipped_during_travel[i] + skipped_during_travel[j];
            int skipped_in_person_meetings = in_person_meetings_before[i] + in_person_meetings_after[j + travel_time - 1];
            
            if (skippable_cnt < skipped_on_travel + skipped_in_person_meetings)
            {
                continue;
            }
            
            int skippable = skippable_cnt - skipped_on_travel;
            int curr_res = no_tasks_before[i] + no_tasks_after[j + travel_time - 1] + skippable;
            res = max(res, curr_res);
        }
    }
    
    cout << res << "\n";
    return 0;
}