Submission #345346

#	Time	Username	Problem	Language	Result	Execution time	Memory
345346		alireza_kaviani	Split the sequence (APIO14_sequence)	C++17	11 / 100	1 ms	512 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define SZ(x)                       ll(x.size())

ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}

const ll MAXN = 1e5 + 10;
const ll MAXK = 210;
const ll LOG = 22;
const ll INF = 2e18;
const ll MOD = 2e9 + 7; // 998244353; // 1e9 + 9;

ll n , k , ptr , A[MAXN] , ps[MAXN] , dp[2][MAXN];
int prv[MAXK][MAXN];
vector<pair<pll , pll>> vec;

ll insect(pll A , pll B){
	ll x = B.Y - A.Y , y = A.X - B.X;
	if(A.X == B.X)	return (A.Y <= B.Y ? -MOD : MOD);
	return (x / y + (x % y > 0));
}

void insert(ll A , ll B , ll ind){
	ll pos = -MOD;
	while(SZ(vec)){
		ll x = insect(vec.back().Y , pll(A , B));
		pos = max(x , vec.back().X.X);
		if(x > vec.back().X.X)	break;
		vec.pop_back();
	}
	if(SZ(vec))	assert(pos > vec.back().X.X);
	ptr = min(ptr , max(0ll , SZ(vec) - 1));
	vec.push_back({{pos , ind} , {A , B}});
}

pll get(ll pos){
	/*ptr = min(ptr , max(0ll , SZ(vec) - 2));
	while(ptr + 1 < SZ(vec) && vec[ptr + 1].X.X <= pos)	ptr++;*/
	pll ans = {0 , 0};
	for(int i = ptr ; i < SZ(vec) ; i++){
		if(ans < pll(vec[i].Y.X * pos + vec[i].Y.Y , vec[i].X.Y)){
			ptr = i;
			ans = max(ans , pll(vec[i].Y.X * pos + vec[i].Y.Y , vec[i].X.Y));
		}
	}
	return ans;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin >> n >> k;
	if(n * n * k >= MAXN)	return 0;
	for(int i = 1 ; i <= n ; i++){
		cin >> A[i];
		ps[i] = ps[i - 1] + A[i];
	}
	for(int i = 1 ; i <= k ; i++){
		for(int j = 1 ; j <= n ; j++){
			insert(ps[j - 1] , dp[1 - i % 2][j - 1] - ps[j - 1] * ps[j - 1] , j - 1);
			pll A = get(ps[j]);
			dp[i % 2][j] = A.X;
			prv[i][j] = A.Y;
		}
		vec = {}; ptr = 0;
	}
	cout << dp[k % 2][n] << endl;
	vector<int> ans;
	int cur = prv[k][n] , ind = k - 1;
	while(cur){
		ans.push_back(cur);
		cur = prv[ind][cur];
		ind--;
	}
	reverse(all(ans));
	for(int i : ans)	cout << i << sep;

    return 0;
}
/*

*/

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