Submission #639241

#	Time	Username	Problem	Language	Result	Execution time	Memory
639241		nttt	Split the sequence (APIO14_sequence)	C++14	0 / 100	605 ms	17800 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 + 3;
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;
int pre[N];
int f[203][N];
int trace[203][N];

void dnc(int g, int l, int r, int from, int to)
{
	if(l > r) return;
	int mid = (l + r)/2;
	for(int i = from; i <= min(to, mid); i++)
	{
		if(f[g][mid] < f[g - 1][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]))
		{
			f[g][mid] = f[g - 1][i - 1] + (pre[mid] - pre[i - 1]) * (pre[n] - pre[mid]);
			trace[g][mid] = i;
		}
	}
	trace[g][mid] = trace[g][mid] - 1;
	dnc(g, l, mid - 1, from, trace[g][mid] + 1);
    dnc(g, mid + 1, r, trace[g][mid] + 1, to);
}
void Solve()
{
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
	{
		int 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, 1, n, 1, n);
	cout << f[k + 1][n] << '\n';

	vector<int> ans;
	int t = trace[k + 1][n];
	ans.pb(t);
	for(int i = k; i >= k - 1; i--)
	{
		t = trace[i][t];
		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: 0 / 11
• Subtask 2: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29