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

int n, k, t;
string dzien;
vector<vector<array<int, 3>>> dp;
#define maxeq(a, b) a = max(a, b)

int sum(int a, int b, char c)
{
    int res = 0;
    for (int i = a; i < b; i++)
    {
        res += (dzien[i] == c);
    }
    return res;
}

/*
1. spotkanie w biurze,
2. zdalne spotkanie,
3. brak obowiązków.
*/

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k >> t;
    cin >> dzien;
    dzien = "#" + dzien;
    dp.resize(n * 2 + 1, vector<array<int, 3>>(k + 2, {{INT_MIN, INT_MIN, INT_MIN}}));
    dp[0][0][0] = 0;

    for (int i = 1; i <= n; i++)
    {
        // cerr << i << ":\n";
        for (int j = 0; j <= k; j++)
        {
            int trip_cost = sum(i, i + t, '2') + sum(i, i + t, '1');
            int trip_end = min(k + 1, j + trip_cost);
            // cout << trip_cost << " trip cost\n";
            // cout << trip_end << " " << i + t - 1 << " after\n";
            maxeq(dp[i + t - 1][trip_end][1], dp[i - 1][j][0]);
            maxeq(dp[i + t - 1][trip_end][2], dp[i - 1][j][1]);

            bool penalty = (dzien[i] != '3');
            
            maxeq(dp[i][j + penalty][0], dp[i - 1][j][0] + 1);
            maxeq(dp[i][j + penalty][2], dp[i - 1][j][2] + 1);
    
            maxeq(dp[i][j][1], dp[i - 1][j][1]);
            if (dzien[i] == '2')
            {
                maxeq(dp[i][j][0], dp[i - 1][j][0]);
                maxeq(dp[i][j][2], dp[i - 1][j][2]);
            }
            if (dzien[i] == '1')
            {
                maxeq(dp[i][j][1], dp[i - 1][j][1]);
            }

            // cerr << j << ": " << dp[i][j][0] << " " << dp[i][j][1] << " " << dp[i][j][2] << "\n";
        }
    }
    int minn = INT_MIN;
    for (int i = 0; i <= k; i++)
    {
        maxeq(minn, dp[n][i][2]);
        // cerr << dp[n][i][2] << "\n";
    }
    for (int i = 0; i <= k; i++)
    {
        maxeq(minn, dp[n][i][0]);
        // cerr << dp[n][i][0] << "\n";
    }
    cout << (minn < 0 ? -1 : minn) << "\n";
}

/*
10 1 2
3233313132

7 0 2
3313233

4 1 1
1331

7 1 2
1331231
*/