QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682677 | #7880. Streak Manipulation | Jokerlove | WA | 0ms | 3608kb | C++14 | 1.4kb | 2024-10-27 16:55:03 | 2024-10-27 16:55:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
long long n,m,k;
long long pre[N];//前缀中0的数量
long long dp[N][6][2];
string s;
bool check(int mid)
{
for (int i = 0; i <= n;i++)
{
for(int j = 0;j<=k;j++)
{
dp[i][j][0]=dp[i][j][1]=0x3f3f3f3f;
}
}
dp[0][0][0] = 0;
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<=k;j++)
{
if(s[i]=='0')
{
dp[i][j][0] = min({dp[i][j][0], dp[i-1][j][0], dp[i-1][j][1]});
dp[i][j][1] = min({dp[i][j][1], dp[i-1][j][1] + 1});
}
else
{
dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][0]);
dp[i][j][1] = min(dp[i][j][1], dp[i-1][j][1]);
}
if (i >= mid && j >= 1)
{
dp[i][j][1] = min((dp[i][j][1]), (dp[i-mid][j-1][0] + pre[i] - pre[i-mid]));
}
}
}
return min(dp[n][k][0], dp[n][k][1]) <= m;
}
int main()
{
cin >> n >> m >> k;
cin >> s;
s = ' ' + s;
for(int i =1;i<= n;i++)
{
pre[i] += (pre[i - 1] + s[i] == '0');
}
int l=0,r=2e5;
while (l<r)
{
int mid = (l + r + 1) >> 1;
if(check(mid))l=mid;
else
r = mid - 1;
}
if(l)
cout << l << '\n';
else
cout << "-1\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3544kb
input:
12 3 3 100100010011
output:
3
result:
wrong answer 1st numbers differ - expected: '2', found: '3'