QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#682493 | #7880. Streak Manipulation | WedonotLikeStudying# | WA | 1ms | 3656kb | C++23 | 748b | 2024-10-27 15:42:14 | 2024-10-27 15:42:15 |
Judging History
answer
#include<bits/stdc++.h>
#define up(a,b,c)for(int a=b;a<=c;++a)
const int N=22e4;
using namespace std;
int n,m,k,f[N],g[N],h[N];
string s;
bool chk(int L)
{
int cc=0;
up(i,0,n-1)
{
cc+=s[i]=='0';
if(i>=L-1)g[i-L+1]=cc,cc-=s[i-L+1]=='0';
}
fill(f,f+n,m+1);
copy(g,g+n-L+1,f+L-1);
up(_,1,k-1)
{
int A=m+1,B=m+1;
up(i,0,n-1)
{
h[i]=B;
if(s[i]=='0')B=min(A,B);
else B=min(A,B+1);
A=min(A,f[i]);
}
fill(f,f+n,m+1);
up(i,0,n-L)f[i+L-1]=min(g[i]+h[i],m+1);
}
int res=m+1;
up(i,0,n-1)res=min(res,f[i]);
return res<=m;
}
int main()
{
cin>>n>>m>>k>>s;
int l=0,r=n/k+1;
while(l+1<r)
{
int mid=(l+r)/2;
if(chk(mid))l=mid;
else r=mid;
}
cout<<(l?l:-1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3572kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
99
result:
ok 1 number(s): "99"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
1000 200 5 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
40
result:
ok 1 number(s): "40"
Test #6:
score: -100
Wrong Answer
time: 1ms
memory: 3588kb
input:
1000 200 5 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
output:
199
result:
wrong answer 1st numbers differ - expected: '-1', found: '199'