记录编号 452669 评测结果 AAAAAAAAAA
题目名称 划分数列 最终得分 100
用户昵称 Gravatar玉带林中挂 是否通过 通过
代码语言 C++ 运行时间 0.046 s
提交时间 2017-09-20 07:00:07 内存使用 0.67 MiB
显示代码纯文本
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <ctype.h>
using namespace std;
#define MAXN 100011
int fast_read()
{
    int r = 0;
    char c;
    bool sig = false;
    while(c = getchar())
    {
        if(c >= '0' && c <= '9')
        {
            r = c^0x30;
            break;
        }else if(c == '-')
            sig = true;
    }
    while(isdigit(c = getchar()))
        r = (r<<3)+(r<<1)+(c^0x30);
    if(sig)return -r;
    return r;
}
int n, t;
int sum[MAXN];
bool check(int m)
{
    int cnt = 0;
    int last = 1;
    for(int i = 1; i <= n; i++)
    {
        if(sum[i] - sum[i-1] > m)return false;  
        if(sum[i] - sum[last-1] > m)
        {
            cnt++;
            last = i;
        }
    }
    return cnt < t;
}
int main()
{
    freopen("seqa.in", "r", stdin);
    freopen("seqa.out", "w", stdout);
    scanf("%d %d", &n, &t);
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i-1]+fast_read();
    int l = 0, r = 0x7fffffff;
    int ans;
    while(l <= r)
    {
        int m = (l+r)>>1;
        if(check(m))ans = m, r = m-1;
        else l = m+1;
    }
    printf("%d\n", ans);
    return 0;
}