D. Array Splitting(后缀数组）

You are given an array 1,2,…, and an integer

You are asked to divide this array into

non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray. Let () be the index of subarray the -th element belongs to. Subarrays are numbered from left to right and from 1 to

Let the cost of division be equal to ∑=1(⋅())

. For example, if =[1,−2,−3,4,−5,6,−7] and we divide it into 3 subbarays in the following way: [1,−2,−3],[4,−5],[6,−7], then the cost of division is equal to 1⋅1−2⋅1−3⋅1+4⋅2−5⋅2+6⋅3−7⋅3=−9

Calculate the maximum cost you can obtain by dividing the array

into

non-empty consecutive subarrays.

Input

The first line contains two integers

and (1≤≤≤3⋅105

The second line contains

integers 1,2,…, (||≤106

Output

Print the maximum cost you can obtain by dividing the array

into

nonempty consecutive subarrays.

Examples

Input

Copy

5 2

-1 -2 5 -4 8

Output

Copy

Input

Copy

7 6

-3 0 -1 -2 -2 -4 -1

Output

Copy

-45

Input

Copy

4 1

3 -1 6 0

Output

Copy

8


题解：将n个数的数组分成k个连续的子数组，并且第i个子数组的权值为i，则我们可以用后缀和。首先我们一定每个数都得至少取一次，则我么一定要取a[1],然后将后面的n-1个数排序，
因为题目要求获得答案最大，并且这后n-1个数我们任意取k-1个都能保证符合题意中的分法，则为了保证答案最大我们就要取比较大的前k-1个了～～

#include<bits/stdc++.h>

#include<iostream>

#include<stdio.h>

#include<iomanip>

#include<stack>

#include<queue>

#include<algorithm>

#include<cstring>

#include<map>

#include<vector>

#include<numeric>

#include<iterator>

#include<cmath>

#define mem(a,x) memset(a,x,sizeof(a));

using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); }

int lcm(int a, int b) { return a * b / gcd(a, b); }

const int INF = 0x3f3f3f3f;

typedef long long ll;

const int mod=1000000007;

typedef pair<int,int>Pi;

typedef pair<ll, ll>Pii;

map<int,int>mp;

map<int, char *>mp1;

map<char *, int>mp2;

map<char, int>mp3;

map<string,int>mp4;

map<char,int>mp5;

const int maxn = 300010;

ll a[maxn];

int read(){

    int flag=1;

    int sum=0;

    char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-')flag=-1;

        c=getchar();

    }

    while(c>='0'&&c<='9'){

        sum=sum*10+c-'0';

        c=getchar();

    }

    return sum*flag;

}

ll Read(){

    int flag=1;

    ll sum=0;

    char c=getchar();

    while(c<'0'||c>'9'){

        if(c=='-')flag=-1;

        c=getchar();

    }

    while(c>='0'&&c<='9'){

        sum=sum*10+c-'0';

        c=getchar();

    }

    return sum*flag;

}

ll quickmul(ll a,ll b){

    ll ans=0;

    while(b){

        if(b&1){

            ans=(ans+a)%mod;

        }

        a=(a+a)%mod;

        b>>=1;

    }

    return ans;

}

ll quickpow(ll a,ll b){

    ll ans=1;

    while(b){

        if(b&1)

            ans=(ans*a)%mod;

        a=(a*a)%mod;

        b>>=1;

    }

    return ans;

}

int main()

{

    int n,k;

    cin>>n>>k;

    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=n;i>=1;i--)a[i]+=a[i+1];

    sort(a+2,a+1+n,greater<ll>());

    ll ans=0;

    for(int i=1;i<=k;i++)ans+=a[i];

    cout<<ans<<endl;

    return 0;

}

巴特西

D. Array Splitting(后缀数组）

最新文章

热门文章