题目的意思是,给你n个连续的序列,有m次操作,每次操作是求某个区间和然后减去c,求能获得的最大值。


比赛的时候真的是脑子短路,这么简单的贪心竟然看不出来,每次看到区间就想到dp,然后就不想做了,心痛啊。不过还是有个坑点,就是长整型,湘大的OJ是要用%I64d输出的。


代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int maxn=100005;
int n, m, c;
LL sum[maxn], ans;
int main()
{
    while(~scanf("%d%d%d", &n, &m, &c)){
        sum[0]=0;
        for(int i=1;i<=n;i++){
            scanf("%I64d", &sum[i]);
            sum[i]+=sum[i-1];
        }
        sort(sum, sum+n+1);
        ans=0;
        for(int i=0;i<m;i++){
            LL val=abs(sum[n-i]-sum[i])-c;
            if(val<=0)break;
            ans+=val;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}