Submission #1198478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198478		PlayVoltz	Split the sequence (APIO14_sequence)	C++20	0 / 100	73 ms	164032 KiB

sequence

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

#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back

deque <pair<pii, int> > convexhull;

int eval(pii line, int x){
	return line.first*x+line.second;
}

pii query(int x){
	while (convexhull.size()>1){
		if (eval(convexhull[0].first, x)<eval(convexhull[1].first, x))convexhull.pop_front();
		else break;
	}
	return mp(eval(convexhull[0].first, x), convexhull[0].second);
}

long double intersect(pii a, pii b){
	return (long double)(b.second-a.second)/(a.first-b.first);
}

void insert(int m, int c, int id){
	pii line = mp(m, c);
	while (convexhull.size()>1){
		int s = convexhull.size();
		if (intersect(convexhull[s-1].first, line)<=intersect(convexhull[s-2].first, line))convexhull.pop_back();
		else break;
	}
	convexhull.push_back(mp(line, id));
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k, a;
	cin>>n>>k;
	vector<int> psum(100005, 0);
	vector<vector<int> > dp(2, vector<int>(100005, 0)), par(205, vector<int>(100005, 0));
	for (int i=1; i<=n; ++i)cin>>a, psum[i]=a+psum[i-1];
	for (int i=1; i<=n; ++i)dp[1][i] = psum[i]*(psum[n]-psum[i]);
	for (int l=2; l<=k; ++l){
		int j=l%2;
		convexhull.clear();
		for (int i=l; i<=n-k+l; ++i){
			insert(psum[i-1], dp[1-j][i-1]-psum[n]*psum[i-1], i-1);
			pii res = query(psum[i]);
			dp[j][i] = res.first+psum[n]*psum[i]-psum[i]*psum[i];
			par[l][i] = res.second;
		}
	}
	int maxnum=INT_MIN, num;
	for (int i=1; i<=n; ++i)if (dp[k%2][i]>maxnum)maxnum=dp[k%2][i], num=i;
	cout<<maxnum<<"\n";
	while (num){
		cout<<num<<" ";
		num = par[k][num];
		--k;
	}
}

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