Submission #1202561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202561		adiyer	Split the sequence (APIO14_sequence)	C++20	100 / 100	553 ms	85884 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 2;

int n, k;
int a[N], sz[201];
int dp[N][201];

pair < ll, int > ans, pro;

ll p[N], s[N];

struct convex_hull{

	int l = 1, r;

	struct line {
	
		int m;
		
		ll b;
		
		int i;

		ll get(ll x){
			return m * 1ll * x + b;
		}

	};

	vector < line > c;

	bool bad(line nw){
		line x = c[c.size() - 2], y = c[c.size() - 1];
		if((x.b - nw.b) * 1ll * (y.m - x.m) == (x.b - y.b) * 1ll * (nw.m - x.m)) return nw.b > y.b;
		return (x.b - nw.b) * 1ll * (y.m - x.m) < (x.b - y.b) * 1ll * (nw.m - x.m); 
	}

	pair < ll, int > eval(ll x){
		if(l >= c.size()) return {0ll, 0};
		while(l + 1 < c.size() && c[l].get(x) < c[l + 1].get(x)) l++;
		return {c[l].get(x), c[l].i};
	}

	void insert_line(line nw){
		if(c.empty()) c.push_back({0ll, 0});
		while(l + 1 < c.size() && bad(nw)) c.pop_back();
		c.push_back(nw);
	}

} hull[2];


void solve(){
	cin >> n >> k;
	for(int i = 0; i <= 200; i++) sz[i] = 1;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) p[i] = p[i - 1] + a[i];
	for(int i = n; i >= 1; i--) s[i] = s[i + 1] + a[i];
	hull[0].insert_line({0, 0, 0});
	for(int lay = 1; lay <= k; lay++){
		bool ly = (lay & 1);
		hull[ly].c.clear();
		for(int i = lay; i < n; i++){
			pro = hull[(ly ^ 1)].eval(-(s[i + 1]));
			pro.first += p[i] * s[i + 1], dp[i][lay] = pro.second;
			if(pro.first >= ans.first) ans = {pro.first, i};
			hull[ly].insert_line({p[i], pro.first, i});
		}
		hull[(ly ^ 1)] = hull[ly];
	}
	int pos = ans.second;
	cout << ans.first << '\n';
	while(k > 0){
		cout << pos << ' ';
		pos = dp[pos][k];
		k--;
	}
}

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

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:72:50: warning: narrowing conversion of 'p[i]' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
   72 |                         hull[ly].insert_line({p[i], pro.first, i});
      |                                               ~~~^

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