VOCARD - Trò chơi chọn bài
Tác giả: ladpro98
Ngôn ngữ: C++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
const int N = 2000006;
using namespace std;
int n, k, l, r, ai, Q[N], F[N];
char str[N];
int main() {
ios :: sync_with_stdio(0); cin.tie();
cin >> n >> k;
cin >> str;
int sum = 0; l = 1, r = 1; Q[1] = 0;
for(int i = 1; i <= n; i++) {
sum += str[i - 1] - '0';
while (l <= r && Q[l] < i - k) l++;
F[i] = sum - F[Q[l]];
while (l <=r && F[Q[r]] >= F[i]) r--;
Q[++r] = i;
}
if (F[n] + F[n] == sum) cout << "NO";
else cout << "YES" << endl << min(F[n], sum - F[n]);
return 0;
}