题目描述

原题地址：COGS BZOJ

思路

合法的n是一个区间，可以分成两次求，二分n的范围。注意有一些关于long long和代码的细节，这个checker还是很好写的

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxl = 100010;
ll mlog[maxl];
int lll, k;
int ck(ll nn)
{
    ll ans = 0, line = 0;
    for (int i = 1; i <= lll; ++i)
    {
        line += mlog[i];
        if (line < 0) line = 0;
        if (line >= nn) ++ans, line = 0;
    }
    if (ans > k) return 1;
    if (ans == k) return 0;
    if (ans < k) return -1;
}
int main()
{
    freopen("autoac.in", "r", stdin);
    freopen("autoac.out", "w", stdout);
    cin >> lll >> k;
    ll rmax = 0, rsum = 0;
    for (int i = 1; i <= lll; ++i)
        cin >> mlog[i], rsum += (mlog[i] > 0 ? mlog[i] : 0), rmax = max(rmax, rsum);
    rmax++;
//================================
    ll maxn = 0, minn = 0;
    ll l = 1, r = rmax, mid;
    while (l + 1 != r)
    {
        mid = (l + r) >> 1;
        int st = ck(mid);
        if(st == 1)
            l = mid;
        else r = mid;
    }
    if (ck(l) == 0) minn = l;
    else if (ck(r) == 0) minn = r;
    else minn = -1;
//================================
    l = 1, r = rmax;
    while(l + 1 != r)
    {
        mid = (l + r) >> 1;
        int st = ck(mid);
        if (st != -1)
            l = mid;
        else r = mid;
    }
    if (ck(r) == 0) maxn = r;
    else if (ck(l) == 0) maxn = l;
    else maxn = -1;
//================================
    if (maxn == -1 && minn == -1)
    {
        cout << -1 << endl;
        return 0;
    }
    cout << minn << ' ' << maxn << endl;
}