Submission #345487

#	Time	Username	Problem	Language	Result	Execution time	Memory
345487		Keshi	Split the sequence (APIO14_sequence)	C++17	100 / 100	674 ms	84780 KiB

sequence

//In the name of God
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 1e5 + 10;
const ll maxk = 205;
const ll mod = 1e9 + 7;
const ll inf = 1e9;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll n, k, a[maxn], ps[maxn], dp[2][maxn];
int par[maxk][maxn];
vector<pll> vec;
vector<int> v2;

void add(ll x, ll y, ll i){
	if(vec.empty()){
		vec.pb(Mp(x, y));
		v2.pb(i);
		return;
	}
	if(vec.back().F == x) return;
	while(Sz(vec) > 1){
		if((y - vec[Sz(vec) - 2].S) * (vec[Sz(vec) - 2].F - vec[Sz(vec) - 1].F) < (vec[Sz(vec) - 1].S - vec[Sz(vec) - 2].S) * (vec[Sz(vec) - 2].F - x)){
          vec.pop_back();
          v2.pop_back();
        }
		else break;
	}
	vec.pb(Mp(x, y));
	v2.pb(i);
	return;
}

int main(){
    fast_io;

	cin >> n >> k;
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
		ps[i] = ps[i - 1] + a[i];
		dp[0][i] = ps[i] * ps[i];
	}
	for(ll i = 1; i <= k; i++){
		vec.clear();
		v2.clear();
		ll p = 0;
		for(ll j = i + 1; j <= n; j++){
			add(-ps[j - 1], ps[j - 1] * ps[j - 1] + dp[i - 1 & 1][j - 1], j - 1);
			p = min(p, Sz(vec) - 1);
			while(p < Sz(vec) - 1 && 2 * ps[j] * (vec[p + 1].F - vec[p].F) <= (vec[p].S - vec[p + 1].S)) p++;
			dp[i & 1][j] = ps[j] * ps[j] + 2 * ps[j] * vec[p].F + vec[p].S;
			par[i][j] = v2[p];
		}
	}
	cout << (ps[n] * ps[n] - dp[k & 1][n]) / 2 << "\n";
	for(ll i = 0; i < k; i++){
		n = par[k - i][n];
		cout << n << " ";
	}

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:60:49: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   60 |    add(-ps[j - 1], ps[j - 1] * ps[j - 1] + dp[i - 1 & 1][j - 1], j - 1);
      |                                               ~~^~~

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