提出 #39214632

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ull unsigned LL
#define db double
#define ldb long double
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define complete_unique(x) (x).erase(unique(all(x)),(x).end());
#define fr(x) freopen(x,"r",stdin);
#define fw(x) freopen(x,"w",stdout);
#define mst(x,a) memset(x,a,sizeof(x));
#define lowbit(x) ((x) & (-(x)))
#define ex0 exit(0);
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define inf 0x3f3f3f3f
#define yes std::cout << "Yes\n"
#define no std::cout << "No\n"
//#pragma GCC optimize(2) // if CE please delete
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
const int base1 = 131;
const int base2 = 13331;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
typedef pair<int, int> hashv;
hashv operator + (hashv a, hashv b) {
	int c1 = a.fi + b.fi, c2 = a.se + b.se;
	if (c1 >= mod1) c1 -= mod1;
	if (c2 >= mod2) c2 -= mod2;
	return mp(c1, c2);
}
hashv operator - (hashv a, hashv b) {
	int c1 = a.fi - b.fi, c2 = a.se - b.se;
	if (c1 < 0) c1 = c1 + mod1;
	if (c2 < 0) c2 = c2 + mod2;
	return mp(c1, c2);
}
hashv operator * (hashv a, hashv b) {
	return mp(1ll * a.fi * b.fi % mod1, 1ll * a.second * b.second % mod2);
}
template <typename T>
inline T qpow(T a, int b, const int mod = 1e9 + 7) //quick_pow
{
	T res = 1;
	while (b)
	{
		if (b & 1) res = (1ll * res * a) % mod;
		a = (1ll * a * a) % mod;
		b >>= 1;
	}
	return res;
}
LL gcd(LL a, LL b)
{
	return b == 0 ? a : gcd(b, a % b);
}
inline char gc() {
	static char buf[1000000], * p1 = buf, * p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read()
{
	T x = 0, flag = 1;
	char c = gc();
	while (c < '0' || c > '9')
	{
		if (c == '-') flag = -1;
		c = gc();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = gc();
	}
	return x * flag;
}
template <typename T>
inline void pr(T x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) pr(x / 10);
	putchar(x % 10 + '0');
}
const int N = 2E6 + 10;
const int M = 4e6 + 10;
int a[N];
int len[N];
int n, m, k;
string s;
int main()
{
	IOS;
	cin >> n >> k;
	cin >> s;
	s = '/' + s + '/';
	int c = 0;
	for (int i = 1; i <= n; i++) {
		if (s[i] == 'X') c++;
	}
	if (k > c) {
		for (int i = 1; i <= n; i++) s[i] = (s[i] == 'X') ? 'Y' : 'X';
		k = n - k;
	}
	if (c == n) {
		cout << min(k - 1, 0);
		return 0;
	}
	int i = 1;
	for (; i <= n; i++) if (s[i] == 'Y') break;
	for (int i = 1; i <= n;) {
		int j = i + 1;
		while (j <= n && s[j] == 'X') {
			j++;
		}
		if (s[j] == 'Y' && s[i] == 'Y') {
			len[j - i - 1]++;
		}
		i = j;
	}
	int ans = 0;
	for (int i = 1; i <= n && k > 0; i++) {
		while (len[i] > 0 && k > 0) {
			if (k >= i) {
				k -= i;
				len[i]--;
				ans += i + 1;
			}
			else {
				ans += k;
				k = 0;
			}
		}
	}
	if (k > 0) ans += k;
	for (int i = 1; i <= n; i++) if (s[i] == s[i - 1] && s[i] == 'Y') ans++;
	cout << ans << endl;
	return 0;
}

提出情報

ジャッジ結果