Educational Codeforces Round 66 D. Array Splitting

Problem - D - Codeforces

概要

n項の数列aと整数kが与えられる。aをk個の連続する部分列に分解し、f(i)：i番目の項が属する部分列の番号とする。Σai * f(i)の最大値を答えよ。

制約

1 ≦ k ≦ n ≦ 3 * 10 ^ 5
|ai| ≦ 10^6

方針

数列の後ろからの累積和s(k) = a[k] + a[k+1] + ... + a[n] を考える。
また、i番目の部分列がp[i]からp[i+1]-1までとする。
このとき、
Σai * f(i)
= 1 * (s(p[1]) - s(p[2])) + 2 * (s(p[2]) - s(p[3])) + ... + k * (s(p[k]) - 0))
= s(p[1]) + s(p[2]) + ... + s(p[k])

よって後ろからの累積和を最大化させるように各p[i]を選ぶ問題に帰着される。
s(p[1])は全ての項の累積和であるので、それ以外のk-1個のp[i]については、
後ろからの累積和のうち上位k-1個となるようなものを選べばよい。

解答

Submission #55476178 - Codeforces

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)

using namespace std;

typedef long long ll;

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n, k;
	cin >> n >> k;

	vector<int> a(n);
	rep(i, n) cin >> a[i];

	ll s = 0;
	vector<ll> b;
	for(int i = n - 1; i >= 1; i--){
		s += a[i];
		b.push_back(s);
	}

	sort(b.begin(), b.end(), greater<ll>());

	ll ans = s + a[0];
	rep(i, k-1){
		ans += b[i];
	}

	cout << ans << endl;
}