QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#663180 | #8783. Cherry Picking | daoqi | WA | 1ms | 3808kb | C++20 | 1.8kb | 2024-10-21 14:00:41 | 2024-10-21 14:00:43 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
using l64 = long double;
template<class T>
struct RMQ {
int n;
std::vector<T> a;
std::vector<std::array<T, 30>> f;
std::function<T(T, T)> func;
RMQ() {};
RMQ(std::vector<T> init_, std::function<T(T, T)> func_) {
work(init_, func_);
}
void work(std::vector<T> &init_) {
work(init_, [&](T x, T y) { return std::max(x, y); });
}
void work(std::vector<T> &init_, std::function<T(T, T)> func_) {
this->a = init_;
this->func = func_;
this->n = a.size();
this->f.assign(n, {});
for (int i = 0; i < n; i++) f[i][0] = a[i];
for (int j = 1; j <= std::__lg(n) + 1; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
f[i][j] = func(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
}
}
T query(int l, int r) {
int k = std::__lg(r - l + 1);
return func(f[l][k], f[r - (1 << k) + 1][k]);
}
};
void DAOQI() {
int n, k;
std::cin >> n >> k;
std::vector<int> rat(n + 1);
for (int i = 1; i <= n; i++)std::cin >> rat[i];
RMQ<int> rmq;
rmq.work(rat, [&](int x, int y) {
return std::min(x, y);
});
std::string s;
std::cin >> s;
s = " " + s;
int ans = 0;
for (int l = 1, r = 1; r <= n; r++) {
if (s[r] == '0') {
l = r + 1;
continue;
}
if (r - l + 1 > k) l++;
if (r - l + 1 == k) {
ans = std::max(ans, rmq.query(l, r));
}
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
//std::cin >> T;
while (T--) DAOQI();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3684kb
input:
5 2 1 2 3 4 5 01101
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
5 2 3 4 5 2 1 10101
output:
0
result:
ok answer is '0'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
1 1 1 1
output:
1
result:
ok answer is '1'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
1 1 1 0
output:
0
result:
ok answer is '0'
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 3580kb
input:
5 3 8 3 5 2 7 10101
output:
0
result:
wrong answer expected '5', found '0'