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
#include <bits/stdc++.h>
using namespace std;
const int MX = 8e3 + 9;
int pref1[MX], pref2[MX];
int main(){
    int n, k, t; cin >> n >> k >> t;
    for(int i = 1; i <= n+1; ++i){
        char ch;
        if(i <= n) cin >> ch;
        else ch = '3';
        if(ch == '2'){
            pref1[i] = pref1[i-1] + 1;
            pref2[i] = pref2[i-1];
        }
        else if(ch == '1'){
            pref2[i] = pref2[i-1] + 1;
            pref1[i] = pref1[i-1];
        }
        else{
            pref1[i] = pref1[i-1];
            pref2[i] = pref2[i-1];
        }
    }
    int score = -1;
    int lostleft, lostright, lost, ck, onlineleft, onlineright, online, restleft, restright, rest, glostleft, glost, glostright;
    lost = pref2[n];
    online = pref1[n];
    ck = k;
    if(ck - lost >= 0){
        score = max(score, n - lost - online + min(ck, online + lost));
    }
    for(int i = t+1; i <= n-t; ++i){
        for(int j = i; j <= n-t; ++j){
            lostleft = pref1[i-1] - pref1[i-t-1] + pref2[i-1] - pref2[i-t-1];
            lostright = pref1[j+t] - pref1[j] + pref2[j+t] - pref2[j];
            lost = lostleft + lostright;
            if(lost > k) continue;
            ck = k-lost;
            glostleft = pref2[i-t-1];
            glostright = pref2[n] - pref2[j+t];
            glost = glostleft + glostright;
            if(glost > ck) continue;
            ck -= glost;
            onlineleft = pref1[i-t-1];
            onlineright = pref1[n] - pref1[j+t];
            online = onlineleft + onlineright;
            restleft = i-t-1 - pref1[i-t-1] - pref2[i-t-1];
            restright = n - (j+t) - pref1[n] + pref1[j+t] - pref2[n] + pref2[j+t];
            rest = restleft + restright;
            score = max(score, rest + glost + min(ck, online));
        }
    }
    cout << score;
}