QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#277665 | #7880. Streak Manipulation | ucup-team059 | WA | 1ms | 3556kb | C++20 | 1.0kb | 2023-12-06 21:18:37 | 2023-12-06 21:18:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i32 = int32_t;
using vi = vector<i32>;
const i32 inf = 1e9;
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
i32 n, m, k;
string s;
cin >> n >> m >> k >> s;
s = " " + s;
vi sum(n + 1);
for (i32 i = 1; i <= n; i++) sum[i] = sum[i - 1] + (s[i] == '0');
auto check = [=](i32 x) {
vector f(n + 1, vi(k + 1, inf));
f[0][0] = 0;
for (i32 i = 1, val; i <= n; i++) {
f[i] = f[i - 1];
if (i >= x and s[i - x] != '1') {
val = sum[i] - sum[i - x];
for (i32 j = 1; j <= k; j++)
f[i][j] = min(f[i][j], f[max(0, i - x - 1)][j - 1] + val);
}
}
return f[n][k] <= m;
};
int l = 0, r = n, res = -1;
for (int mid; l <= r;) {
mid = (l + r) / 2;
if (check(mid)) res = mid, l = mid + 1;
else r = mid - 1;
}
cout << res << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3476kb
input:
4 4 4 0000
output:
0
result:
wrong answer 1st numbers differ - expected: '-1', found: '0'