// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc300/tasks/abc300_f
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.
#include "Other/binary_search.hpp"
#include "DataStructure/nth_accumulater.hpp"
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long N, M, K;
cin >> N >> M >> K;
string S;
cin >> S;
vector<int> x_cnt(N);
for (int i = 0; i < N; i++)
{
if (S[i] == 'x')
{
x_cnt[i]++;
}
}
nthAccumulater<long long, 1> nth_accumulator(x_cnt);
long long ans = 0;
for (int l = 0; l < N; l++)
{
auto check = [&](long long r) -> bool
{
return nth_accumulator.cyclic_sum({l}, {r}) <= K;
};
long long max_r = bin_search<long long>(l, N * M + 1, check);
long long len = max_r - l;
ans = max(ans, len);
}
cout << ans << endl;
return 0;
}
#line 1 "test/DataStructure/nth_accumulater/abc300-f.cpp"
// competitive-verifier: PROBLEM https://atcoder.jp/contests/abc300/tasks/abc300_f
// competitive-verifier: IGNORE
// AtCoder's test cases are now private.
#line 1 "Other/binary_search.hpp"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
enable_if_t<is_integral_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
while (max(ok, ng) - min(ok, ng) > 1)
{
T mid = midpoint(ok, ng);
(check(mid) ? ok : ng) = mid;
}
return ok;
}
template <typename T>
enable_if_t<is_floating_point_v<T>, T>
bin_search(T ok, T ng, function<bool(T)> check)
{
// midpointが成立するように浮動小数型を整数型にbit_castするクラス
class OrderedBitcastFloat
{
public:
using UInt = conditional_t<sizeof(T) == 4, uint32_t, conditional_t<sizeof(T) == 8, uint64_t, void>>;
static_assert(!is_same_v<UInt, void>, "T must be float(4), double(8)");
T real; // 元の実数
UInt int_key; // マッピング整数
OrderedBitcastFloat(T x) : real(x), int_key(real_to_int_key(x)) {}
OrderedBitcastFloat(UInt u) : real(int_key_to_real(u)), int_key(u) {}
private:
static constexpr UInt msb()
{
return UInt(1) << (8 * sizeof(UInt) - 1);
}
// 実数 → マッピング整数
static UInt real_to_int_key(T x)
{
UInt bits = bit_cast<UInt>(x);
if (bits & msb())
{
// 符号ビット＝1（負数領域）：反転
return ~bits;
}
else
{
// 符号ビット＝0（正数領域）：MSB bit を足してオフセット
return bits | msb();
}
}
// マッピング整数 → 実数
static T int_key_to_real(UInt u)
{
UInt bits;
if (u & msb())
{
// MSB=1 → 正数領域：MSBを落とす
bits = u & ~msb();
}
else
{
// MSB=0 → 負数領域：反転を戻す
bits = ~u;
}
return bit_cast<T>(bits);
}
};
OrderedBitcastFloat temp_ok(ok), temp_ng(ng);
while (max(temp_ok.int_key, temp_ng.int_key) - min(temp_ok.int_key, temp_ng.int_key) > 1)
{
OrderedBitcastFloat mid(midpoint(temp_ok.int_key, temp_ng.int_key));
(check(mid.real) ? temp_ok : temp_ng) = mid;
}
return temp_ok.real;
}
#line 2 "DataStructure/nth_accumulater.hpp"
using namespace std;
template <typename T, int DIMENSION_SIZE>
class nthAccumulater
{
private:
vector<T> values;
array<int, DIMENSION_SIZE> sizes;
array<int, DIMENSION_SIZE + 1> sum_sizes;
void init()
{
int sum_size = 1;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
assert(0 < sizes[i]);
sum_sizes[i] = sum_size;
sum_size *= sizes[i] + 1; // 0が含まれるので+1する
}
sum_sizes[DIMENSION_SIZE] = sum_size;
assert(0 < sum_size);
values.resize(sum_size);
}
int get_index(const array<int, DIMENSION_SIZE> &indexes)
{
int result = 0;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
result += indexes[i] * sum_sizes[i];
}
return result;
}
array<int, DIMENSION_SIZE> get_index(int index)
{
assert(0 <= index && index < sum_sizes[DIMENSION_SIZE]);
array<int, DIMENSION_SIZE> indexes;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
indexes[i] = index % (sizes[i] + 1);
index /= (sizes[i] + 1);
}
return indexes;
}
void build()
{
for (int dimension = 0; dimension < DIMENSION_SIZE; dimension++)
{
for (int i = 0; i < sum_sizes[DIMENSION_SIZE]; i++)
{
array<int, DIMENSION_SIZE> index = get_index(i);
if (index[dimension] == sizes[dimension])
{
continue;
}
array<int, DIMENSION_SIZE> next_index = index;
next_index[dimension]++;
set(next_index, get(index) + get(next_index));
}
}
}
T sum_from_origin(const unsigned int &bit_mask, const array<long long, DIMENSION_SIZE> &indexes)
{
T result = 0;
unsigned int sub_bit = bit_mask;
do
{
T count = 1;
array<int, DIMENSION_SIZE> query_index;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
if ((sub_bit >> i) & 1)
{
count *= indexes[i] / sizes[i];
query_index[i] = sizes[i];
}
else
{
count *= 1;
query_index[i] = indexes[i] % sizes[i];
}
}
result += count * get(query_index);
sub_bit = (sub_bit - 1) & bit_mask;
} while (sub_bit != bit_mask);
return result;
}
template <typename V>
void set_sizes(const V &v, int depth = 0)
{
if constexpr (is_arithmetic_v<V>)
{
return;
}
else
{
sizes[depth] = v.size();
set_sizes(v[0], depth + 1);
}
}
template <typename V>
void set_values(const V &v, array<int, DIMENSION_SIZE> &index, int depth = 0)
{
if constexpr (is_arithmetic_v<V>)
{
set(index, v);
return;
}
else
{
for (int i = 0; i < (int)v.size(); ++i)
{
index[depth] = i + 1;
set_values(v[i], index, depth + 1);
}
}
}
public:
template <typename V>
nthAccumulater(const vector<V> &v)
{
set_sizes(v);
init();
array<int, DIMENSION_SIZE> index;
set_values(v, index);
build();
}
T get(const array<int, DIMENSION_SIZE> &indexes)
{
int index = get_index(indexes);
return get(index);
}
T get(const int &index)
{
assert(0 <= index && index < sum_sizes[DIMENSION_SIZE]);
return values[index];
}
void set(const array<int, DIMENSION_SIZE> &indexes, const T &value)
{
int index = get_index(indexes);
set(index, value);
}
void set(const int &index, const T &value)
{
assert(0 <= index && index < sum_sizes[DIMENSION_SIZE]);
values[index] = value;
}
T sum(const array<long long, DIMENSION_SIZE> &l, const array<long long, DIMENSION_SIZE> &r)
{
for (int i = 0; i < DIMENSION_SIZE; i++)
{
assert(0 <= l[i] && l[i] < r[i] && r[i] <= sizes[i]);
}
T result = 0;
for (unsigned int bit = 0; bit < (1 << DIMENSION_SIZE); bit++)
{
int index = 0;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
index += (((bit >> i) & 1) ? r[i] : l[i]) * sum_sizes[i];
}
int one_count = popcount(bit);
T sign = (one_count % 2) == (DIMENSION_SIZE % 2) ? 1 : -1;
result += sign * get(index);
}
return result;
}
T cyclic_sum(array<long long, DIMENSION_SIZE> l, array<long long, DIMENSION_SIZE> r)
{
for (int i = 0; i < DIMENSION_SIZE; i++)
{
assert(l[i] < r[i]);
}
// lの値が負数の場合、正数に変換する
for (int i = 0; i < DIMENSION_SIZE; i++)
{
if (l[i] < 0)
{
long long mod = sizes[i];
long long next_l = (l[i] % mod + mod) % mod;
r[i] += next_l - l[i];
l[i] = next_l;
}
}
T result = 0;
for (unsigned int bit = 0; bit < (1 << DIMENSION_SIZE); bit++)
{
array<long long, DIMENSION_SIZE> indexes;
unsigned int bit_mask = 0;
for (int i = 0; i < DIMENSION_SIZE; i++)
{
indexes[i] = ((bit >> i) & 1) ? r[i] : l[i];
if (sizes[i] <= indexes[i])
{
bit_mask |= (1 << i);
}
}
int one_count = popcount(bit);
T sign = (one_count % 2) == (DIMENSION_SIZE % 2) ? 1 : -1;
result += sign * sum_from_origin(bit_mask, indexes);
}
return result;
}
};
#line 8 "test/DataStructure/nth_accumulater/abc300-f.cpp"
using namespace std;
int main()
{
long long N, M, K;
cin >> N >> M >> K;
string S;
cin >> S;
vector<int> x_cnt(N);
for (int i = 0; i < N; i++)
{
if (S[i] == 'x')
{
x_cnt[i]++;
}
}
nthAccumulater<long long, 1> nth_accumulator(x_cnt);
long long ans = 0;
for (int l = 0; l < N; l++)
{
auto check = [&](long long r) -> bool
{
return nth_accumulator.cyclic_sum({l}, {r}) <= K;
};
long long max_r = bin_search<long long>(l, N * M + 1, check);
long long len = max_r - l;
ans = max(ans, len);
}
cout << ans << endl;
return 0;
}
test/DataStructure/nth_accumulater/abc300-f.cpp 
n次元累積和 (DataStructure/nth_accumulater.hpp)