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

int main(){
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int N, skip, T;
	cin >> N >> skip >> T;
	string S;
	cin >> S;
	assert(N == (int)S.size());
	int meetings = 0;
	for(char c : S) if(c != '3') meetings += 1;
	vector<vector<int> > psums(4, vector<int>(N+1, 0));
	for(int i = 0; i < N; i++){
		psums[1][i+1] = psums[1][i] + (S[i] == '1');
		psums[2][i+1] = psums[2][i] + (S[i] == '2');
		psums[3][i+1] = psums[3][i] + (S[i] == '3');
	}
	skip = min(skip, meetings);
	int need_go = meetings - skip;
	int ans = -1;
	// remote only
	if(psums[2][N] >= need_go){
		ans = N - need_go;
	} else {
		// assume you attend exactly need_go meetings
		// skip exactly skip meetings
		vector<int> best_lskip(N+1, -1);
		for(int x = 0; x <= N; x++){
			if(x >= T){
				int lscore = psums[3][x];
				int lskip = psums[1][x] + (psums[2][x] - psums[2][x-T]);
				best_lskip[lskip] = max(best_lskip[lskip], lscore);
			}
			if(x+T <= N){
				int rscore = psums[3][N] - psums[3][x];
				int rskip = psums[1][N] - psums[1][x] + (psums[2][x+T] - psums[2][x]);
				if(rskip <= skip && best_lskip[skip - rskip] >= 0){
					int tot_score = best_lskip[skip - rskip] + rscore;
					int think = tot_score + meetings - need_go - T - T;
					assert(think >= 0);
					ans = max(ans, think);
				}
			}
		}
	}
	cout << ans << '\n';
}