当前位置:首页 > 瞎暴力 > XTU 1264 Partial Sum

XTU 1264 Partial Sum

Partial Sum

Bobo has a integer sequence a1,a2,,an of length n. Each time, he selects two ends 0l<rn and add |rj=l+1aj|C into a counter which is zero initially. He repeats the selection for at most m times.

If each end can be selected at most once (either as left or right), find out the maximum sum Bobo may have.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains three integers nmC. The second line contains n integers a1,a2,,an.

  • 2n105
  • 12mn+1
  • |ai|,C104
  • The sum of 

    n

     does not exceed 

    106

    .

Output

For each test cases, output an integer which denotes the maximum.

Sample Input

4 1 1
-1 2 2 -1
4 2 1
-1 2 2 -1
4 2 2
-1 2 2 -1
4 2 10
-1 2 2 -1

Sample Output

3
4
2
0

题意 从0~n中取两个数   最多取m次  可以一次不取   比如取到的是2 5  那么 ans+=a3+a4+a5-C

求ans的最大值

保存前缀和  如 sumi=a1+a2+a3..+ai   求  a3-a6的和 用sum6-sum2即可 

把前缀和排序 那么 用最大的减去最小的 因为题目求的是绝对值 所以 求最大的跨度就好了 没看到绝对值- - 想了好久

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;

#define ll __int64
const int N=100005;

int main()
{
    ll n,m,c,a,sum[N];
    while(~scanf("%I64d %I64d %I64d",&n,&m,&c))
    {
        sum[0]=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%I64d",&a);
            sum[i]=sum[i-1]+a;
        }
        sort(sum,sum+n+1);
        int l=n,s=0;
        ll ans=0;
        for(int i=0; i<m; i++)
        {
            ll t=abs(sum[n-i]-sum[i])-c;
            if(t<=0) break;
            ans+=t;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=454

上一篇:XTU 1267 Highway

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。