Submission #543223

#	Time	Username	Problem	Language	Result	Execution time	Memory
543223		fuad27	Split the sequence (APIO14_sequence)	C++17	100 / 100	773 ms	86152 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1000'10;
vector<ll> dp[2];
ll pref[N];
ll arr[N];
int pre[N][210];
bool slope(ll a, ll b, ll c) {
	return (((dp[0][a] - dp[0][b])*(-pref[c]+pref[b])) >= ((dp[0][b] - dp[0][c])*(-pref[b] + pref[a])));
/* slope(cur, dq[0]) >= slope(dq[0], dq[1])

   
   */
}
ll val(ll idx, ll x) {
	return (-pref[idx]*x) + dp[0][idx];
}
int32_t 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];
	if(n == 2) {
		long long ans = arr[0] * arr[1];
		cout << ans << "\n";
		cout << 1 << "\n";
		return 0;
	}
	for(int i= 0;i<=n;i++) {
		for(int j = 0;j<=k+1;j++) {
			pre[i][j] = -1;
		}
	}
	deque<ll> dq;
	for(int j = 1;j<=k;j++) {
		dq.clear();
		for(int i = 0;i<n;i++) {
			ll cur = i, x = pref[n-1]-pref[i], ans = 0;
			if(j > 1) {
			while(dq.size() >= 2 && val(dq.back(), x) <=
			val(dq[dq.size()-2], x))dq.pop_back();
			}
			if(dq.size()){
				int z = dq.back();
				ans = dp[0][z] + (pref[i]-pref[z])*(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;
			if(j > 1 and i!=n-2) {
			while(dq.size() >= 2 && slope(cur, dq[0], dq[1]))dq.pop_front();
			dq.push_front(cur);
			}
//			cout << dp[1][i] << " ";
		}
//		cout << "\n";
		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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29