QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#275506 | #7880. Streak Manipulation | pengpeng_fudan# | WA | 1ms | 7688kb | C++17 | 1.5kb | 2023-12-04 19:40:21 | 2023-12-04 19:40:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int inf=1e8+7;
const int N=2e5+5;
const int K=7;
int n,m,k;
char s[N];
int dp[N][K],minn[N][K];
int cnt[N][2],pre[N];
int check(int mid){
for(int i=0;i<=n;i++)
for(int j=0;j<=k;j++){
dp[i][j]=inf;
minn[i][j]=inf;
}
for(int i=0;i<=n;i++) dp[i][0]=minn[i][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
if(i>=mid){
dp[i][j]=cnt[i][0]-cnt[i-mid][0]+minn[pre[i-mid]][j-1];
}
minn[i][j]=min(dp[i][j],minn[i-1][j]);
}
}
int ans=inf;
for(int i=1;i<=n;i++) ans=min(ans,dp[i][k]);
return ans<=m;
}
int binary(){
int l=1,r=n,mid;
int ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
ans=mid;
}else r=mid-1;
}
return ans;
}
void solve(){
cin>>n>>m>>k;
cin>>s+1;
for(int i=1;i<=n;i++){
int d=s[i]-'0';
cnt[i][d]++;
if(d==1) pre[i]=i;
if(s[i]=='0') continue;
if(i>1&&s[i-1]=='1') pre[i]=pre[i-1];
}
for(int i=1;i<=n;i++){
cnt[i][0]+=cnt[i-1][0];
cnt[i][1]+=cnt[i-1][1];
if(pre[i]==0) pre[i]=i;
else pre[i]=pre[i]-1;
}
int ans=binary();
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int _=1;
// cin>>_;
while(_--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7448kb
input:
8 3 2 10110110
output:
3
result:
ok 1 number(s): "3"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7688kb
input:
12 3 3 100100010011
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 7560kb
input:
4 4 4 0000
output:
1
result:
wrong answer 1st numbers differ - expected: '-1', found: '1'