# P4343 [SHOI2015]自动刷题机()-其他

## P4343 [SHOI2015]自动刷题机()

https://www.luogu.com.cn/problem/P4343

``````#include <iostream>
using namespace std ; const int N=1e5+2;
#define int long long
const int inf=1e15;
int a[N],n,m;

int cal(int x){
int t=0,s=0;
for(int i=1;i<=n;i++){
s=max(s+a[i],0ll);
if(s>=x) s=0,t++;
}
return t;
}
void solve(){
int ans1=-1,ans2=-1 ;
int t;
int l,r,md;
l=1,r=inf;
while(l<=r){
md=(l+r)/2;
if((t=cal(md))<=m){
r=md-1;
if(t==m) ans1=md;
}
else l=md+1;
}

l=1,r=inf;
while(l<=r){
md=(l+r)/2;
if((t=cal(md))>=m){
l=md+1;
if(t==m) ans2=md;
}
else r=md-1;
}
if(ans1==-1) cout<<-1<<endl;
else cout<<ans1<<' '<<ans2<<endl;
}

signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
solve();
}

``````
————————

https://www.luogu.com.cn/problem/P4343

``````#include <iostream>
using namespace std ; const int N=1e5+2;
#define int long long
const int inf=1e15;
int a[N],n,m;

int cal(int x){
int t=0,s=0;
for(int i=1;i<=n;i++){
s=max(s+a[i],0ll);
if(s>=x) s=0,t++;
}
return t;
}
void solve(){
int ans1=-1,ans2=-1 ;
int t;
int l,r,md;
l=1,r=inf;
while(l<=r){
md=(l+r)/2;
if((t=cal(md))<=m){
r=md-1;
if(t==m) ans1=md;
}
else l=md+1;
}

l=1,r=inf;
while(l<=r){
md=(l+r)/2;
if((t=cal(md))>=m){
l=md+1;
if(t==m) ans2=md;
}
else r=md-1;
}
if(ans1==-1) cout<<-1<<endl;
else cout<<ans1<<' '<<ans2<<endl;
}

signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
solve();
}

``````