QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#576751 | #7880. Streak Manipulation | libantian# | WA | 1ms | 6020kb | C++23 | 2.0kb | 2024-09-19 21:59:55 | 2024-09-19 21:59:56 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define all(_a) _a.begin(),_a.end()
const int N=200010;
int a[N],s[N],last[N];
int n,m,k;
bool check(int x){
vector<vector<int>> dp(n+2,vector<int>(k+1,INF));
dp[0][0]=0;
for(int i=1;i<=n+1;i++){
dp[i][0]=dp[i-1][0];
if(a[i]==1)continue;
for(int j=1;j<=k;j++){
dp[i][j]=min(dp[i][j],dp[i-1][j]);
if(i-x-1>=0){
//cout<<last[i-x-1]<<" "<<i<<endl;
dp[i][j]=min(dp[i][j],dp[last[i-x-1]][j-1]+(i-1-last[i-x-1]-(s[i-1]-s[last[i-x-1]])));
}
}
}
/*
for(int j=0;j<=k;j++){
cout<<j<<endl;
for(int i=1;i<=n;i++)cout<<dp[i][j]<<" ";
cout<<endl;
}
*/
return dp[n+1][k]<=m;
}
void solve(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
char x;
cin>>x;
a[i]=x-'0';
s[i]=s[i-1]+a[i];
}
s[n+1]=s[n];
int mx=0;
for(int i=1;i<=n;i++){
int j=i;
while(j+1<=n&&a[j+1]==a[i])j++;
if(a[i]==1){
for(int k=i;k<=j;k++)last[k]=i-1;
i=j;
mx++;
continue;
}
int len=j-i+1;
for(int k=i;k<=j;k++)last[k]=k;
if(i==1&&j==n)mx+=(len+1)/2;
else if(i==1||j==n)mx+=(len)/2;
else mx+=(len-1)/2;
i=j;
}
//for(int i=1;i<=n;i++)cout<<last[i]<<" ";
//cout<<endl;
if(mx<k){
cout<<-1<<endl;
return ;
}
//cout<<check(4);
int l=1,r=n;;
while(l<r){
int mid=l+r+1>>1;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<l;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T=1;
//cin>>T;
while(T--) solve();
}
/*
8 3 2
10110110
3
12 3 3
100100010011
2
4 4 4
0000
-1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5856kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5852kb
input:
4 4 4 0000
output:
-1
result:
ok 1 number(s): "-1"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 6020kb
input:
1000 200 5 0001001000101001110010011001101010110101101100010100111110111111010010001100100111100101011100011101011001110010111100100100011001010011000100011111010110100001101110101001110000001000111010000111110100111101100110011010011111000111101001010011000111010111010100101111100000100001011001010...
output:
85
result:
wrong answer 1st numbers differ - expected: '99', found: '85'