QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273944 | #7880. Streak Manipulation | ucup-team1766# | WA | 1ms | 3576kb | C++23 | 1.7kb | 2023-12-03 06:36:19 | 2023-12-03 06:36:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int rsum(int psum[], int l, int r) {
if (l == 0) {
return psum[r];
}
return psum[r] - psum[l - 1];
}
bool possible(int n, int m, int k, bool a[], int psum[], int x) {
int l_bounds[n];
int l = n - 1;
for (int i = n - 1; i >= 0; i--) {
while (l > 0 && i - l + 1 < x) {
l--;
}
while (l > 0 && a[l - 1]) {
l--;
}
if (l <= i - x + 1) {
l_bounds[i] = l;
} else {
l_bounds[i] = -1;
}
}
// dp[i][j] = min number of 0s turned into 1s in order to create j streaks of at least x using 0...i
int dp[n][k + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= k; j++) {
dp[i][j] = n + 1;
}
}
bool res = false;
for (int i = 0; i < n; i++) {
if (i < n - 1 && a[i + 1]) {
continue;
}
for (int j = 1; j <= k; j++) {
if (i > 0) {
dp[i][j] = dp[i - 1][j];
}
if (l_bounds[i] != -1) {
int cost = i - l_bounds[i] + 1 - rsum(psum, l_bounds[i], i);
int ll = l_bounds[i] - 2;
if (j == 1) {
dp[i][j] = min(dp[i][j], cost);
} else if (ll >= 0 && dp[ll][j - 1] != n + 1) {
dp[i][j] = min(dp[i][j], dp[ll][j - 1] + cost);
}
}
if (j == k && dp[i][j] <= m) {
res = true;
}
}
}
return res;
}
int main() {
int n, m, k;
cin >> n >> m >> k;
string s;
cin >> s;
bool a[n];
int psum[n] = {0};
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
a[i] = 1;
} else {
a[i] = 0;
}
psum[i] = (i > 0 ? psum[i - 1] : 0) + a[i];
}
int l = 1;
int r = n;
int res = -1;
while (l <= r) {
int m = (l + r) / 2;
if (possible(n, m, k, a, psum, m)) {
res = m;
l = m + 1;
} else {
r = m - 1;
}
}
cout << res << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3468kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3576kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
6
result:
wrong answer 1st numbers differ - expected: '99', found: '6'