QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#273255 | #7880. Streak Manipulation | ucup-team484# | WA | 1ms | 3468kb | C++17 | 1.3kb | 2023-12-02 22:28:35 | 2023-12-02 22:28:37 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m, k; cin >> n >> m >> k;
string s; cin >> s;
vector<int> pref(n + 1);
for (int i = 0; i < n; i++) {
pref[i] = (s[i] == '0');
if (i > 0)
pref[i] += pref[i - 1];
}
pref[n] = pref[n - 1];
auto ok = [&](int C) {
vector<vector<int>> dp(k + 1, vector<int>(n + 1, mod));
vector<int> nx(n + 1), sm(n + 1);
for (int i = 0; i < n; i++) {
nx[i] = min(n, max(i + C, i > 0 ? nx[i - 1] : 0));
while (nx[i] < n && s[nx[i]] == '1')
nx[i]++;
sm[i] = pref[nx[i] - 1];
if (i > 0)
sm[i] -= pref[i - 1];
if (i == 0 || s[i - 1] == '0')
dp[1][nx[i]] = sm[i];
}
for (int i = 1; i < k; i++)
for (int j = 1; j < n; j++)
if (nx[j] - j >= C)
dp[i + 1][nx[j]] = min(dp[i + 1][nx[j]], dp[i][j - 1] + sm[j]);
for (int i = 0; i <= n; i++)
if (dp[k][i] <= m)
return 1;
return 0;
};
int lo = 1, hi = n;
while (lo <= hi) {
int mi = (lo + hi) / 2;
if (ok(mi))
lo = mi + 1;
else
hi = mi - 1;
}
if (hi == 0)
hi = -1;
cout << hi << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3392kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: -100
Wrong Answer
time: 1ms
memory: 3468kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
90
result:
wrong answer 1st numbers differ - expected: '99', found: '90'