Submission #543203

#	Time	Username	Problem	Language	Result	Execution time	Memory
543203		fuad27	Split the sequence (APIO14_sequence)	C++17	0 / 100	53 ms	82200 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000'10;
vector<int> dp[2];
ll pref[N];
ll arr[N];
int pre[N][201];
ld slope(ll a, ll b) {
	return (ld)(dp[0][a] - dp[0][b])/(-pref[b]+pref[a]);
}
ll val(ll idx, ll x) {
	return (-pref[idx]*x) + dp[0][idx];
}
int main () {
	ll n, k;
	cin >> n >> k;
	for(int i = 0;i<n;i++)
		cin >> arr[i];
	pref[0] = arr[0];
	for(int i = 0;i<2;i++)dp[i].resize(n+1);
	for(int i = 1;i<n;i++)pref[i] = pref[i-1]+arr[i];
	for(int i = 0;i<=n;i++)pre[i][0] = -1;
	for(int j = 1;j<=k;j++) {
		deque<ll> dq;
		for(int i = 0;i<n;i++) {
			ll cur = i, x = pref[n-1]-pref[i], ans = 0;
			while(dq.size() >= 2 && val(dq.back(), x) <=
			val(dq[dq.size()-2], x))dq.pop_back();
			if(dq.size()){
				ans = val(dq.back(), x) + pref[i]*(pref[n-1]-pref[i]);
				pre[i][j] = dq.back();
			}
			else {
				ans = pref[i]*(pref[n-1]-pref[i]);
				pre[i][j] = -1;
			}
			dp[1][i] = ans;
			while(dq.size() >= 2 && slope(cur, dq[0])
			>= slope(dq[0], dq[1]))dq.pop_front();
			dq.push_front(cur);
		}
		dp[0].swap(dp[1]);
	}
	ll mx = -1, idx = -1;
	for(int i = 0;i<n;i++) {
		if(dp[0][i] >= mx) {
			mx = dp[0][i];
			idx = i;
		}
	}
	cout << mx << "\n";
	while(idx!=-1 and k > 0) {
		cout << idx+1 << " ";
		idx = pre[idx][k];
		k--;
	}
	cout << "\n";
}

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