思路

用数组把字符串存下来，然后二分出答案，再检查答案是否满足要求。
检查答案是否满足要求时，贪心地找最少有多少段表示的数小于等于答案，可以用 $cnt$ 记录，当结束后 $cnt \le k$ 时，即满足要求。

Code

#include<bits/stdc++.h>
#define int long long
#define REP(i,a,b,c) for(int i=a;i<=b;i+=c)
#define PER(i,a,b,c) for(int i=a;i>=b;i-=c)
using ll = long long; 
using namespace std;
const int N=1e6+5;
int n,k,a[N],ans;
string s;
bool check(int x){
    int cnta=0,cntb=0,cnt=0;
    for(int i=1;i<=n;i++){
    	if(a[i])cnta++; else cntb++;
        if(cnta*cntb>x){
        	cnt++;cnta=0;cntb=0;
        	if(a[i])cnta++; else cntb++;
		}
    }
    return cnt<k;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k>>s;
    int l=0,r=250000000000;//当n=10^6、s有500000个0和500000个1、k=1时，r最大，为(500000)^2
    REP(i,0,n-1,1) a[i+1]=s[i]-'0';
    while(l<=r){
        int mid=l+r>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
}