Submission #1088226

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088226		Nurislam	Split the sequence (APIO14_sequence)	C++17	0 / 100	19 ms	12364 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long

template <class F, class _S>
bool chmin(F &u, const _S &v){
	bool flag = false;
	if ( u > v ){
		u = v; flag |= true;
	}
	return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
	bool flag = false;
	if ( u < v ){
		u = v; flag |= true;
	}
	return flag;
}
const int N = 1e6+50, inf = 1e17;
//int mod = 998244353
//int mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)

struct line{
	int m, c, i;
	
	line(int _m,int _c, int _i) : m(_m), c(_c), i(_i){
	};
	
	int calc(int x){
		return m * x + c;
	};
	
	double xnt(line & other){
		return (long double)(c - other.c)/(m - other.m);
	};
};

void solve(){
	int n, k;
	cin >> n >> k;
	vector<int> v(n+1);
	for(int i = 1; i<= n; i++){cin >> v[i];v[i] += v[i-1];}
	
	vector<vector<int>> dp(2, vector<int> (n+2, 0));
	vector<vector<int>> from(n+2, vector<int> (k+2));
	
	for(int j = 1; j <= k; j++){
		//cout << 1 << '\n';
		deque<line> dq;
		dq.pb({0,0,0});
		for(int i = 1; i <= n; i++){
			int ps = v[n] - v[i];
			while(dq.size() > 1 && dq.back().calc(ps) < dq[dq.size()-2].calc(ps))
				dq.pop_back();
				
			dp[1][i] = dq.back().calc(ps) + v[i] * ps;
			from[i][j] = dq.back().i;
			
			line nw = {-v[i], dp[0][i], i};
			while(dq.size() > 1 && nw.xnt(dq[0]) > dq[0].xnt(dq[1]))
				dq.pop_front();
			
			dq.push_front(nw);
		}
		dp[0] = dp[1];
	}
	pair<int,int> ans = {-1, 0};
	for(int i = 1; i < n; i++){
		ans = max(ans, {dp[0][i], i});
	}
	cout << ans.ff << '\n';
	vector<int> res;
	while(ans.ss > 0 && k > 0){
		res.pb(ans.ss);
		ans.ss = from[ans.ss][k--];
	}reverse(all(res));
	
	
	for(int i:res)cout << i << ' ';
	cout << '\n';
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}
}
 
 
 
 
 
 
 
 
 
 
 
 
 

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