Submission #639256

#	Time	Username	Problem	Language	Result	Execution time	Memory
639256		nttt	Split the sequence (APIO14_sequence)	C++14	100 / 100	1051 ms	81504 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define task "name" 

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 1e5 + 2;
const int BASE = 10;
const int LOG = 20;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}

int n, k;
ll pre[N];
ll f[2][N];
int trace[202][N];

void dnc(int g, int l, int r, int from, int to)
{
	if(l > r) return;
	int mid = (l + r)/2;
	pair<long long, int> best(-oo, 0);
	int last = (1 ^ (g & 1));
	int cur = last ^ 1;
	for(int i = from; i <= min(to, mid); i++)
	{
		maximize(best, mp(f[last][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]), i));
	}
	f[cur][mid] = best.fi;
	trace[g][mid] = best.se - 1;
	dnc(g, l, mid - 1, from, best.se);
    dnc(g, mid + 1, r, best.se, to);
}
void Solve()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		ll a;
		cin >> a;
		pre[i] = pre[i - 1] + a;
	}

	for(int i = 1; i <= n; i++) f[1][i] = pre[i] * (pre[n] - pre[i]);
	for(int i = 2; i <= k + 1; i++)
		dnc(i, i, n, 1, n);
	cout << f[(k & 1) ^ 1][n] << '\n';

	vector<int> ans;
	int t = trace[k + 1][n];
	ans.pb(t);
	for(int i = k; i >= 2; i--)
	{
		t = trace[i][t];
		if (t == 0) {
			break;
		}
		ans.pb(t);
	}
	reverse(all(ans));
	for(int i : ans) cout << i << " ";

}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T = 1;
	//cin >> T;
	while(T--)
	{
		Solve();
	}
	
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29