제출 #345378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345378		alireza_kaviani	수열 (APIO14_sequence)	C++17	100 / 100	779 ms	85080 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);
	if(y < 0)	y *= -1 , x *= -1;
	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++;
	return {vec[ptr].Y.X * pos + vec[ptr].Y.Y , vec[ptr].X.Y};
}

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

	cin >> n >> k;
	for(int i = 1 ; i <= n ; i++){
		cin >> A[i];
		ps[i] = ps[i - 1] + A[i];
	}
	//cout << (-2 / 3) << endl;
	//cout << (-2 % 3) << endl;
	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: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29