Submission #92753

#	Time	Username	Problem	Language	Result	Execution time	Memory
92753		davitmarg	Split the sequence (APIO14_sequence)	C++17	100 / 100	1388 ms	87840 KiB

sequence

/*
DEATH-MATCH
Davit-Marg
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <iterator>
#include <ctype.h>
#include <stdlib.h>  
#include <cassert>
#include <fstream>  
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
using namespace std;
int n,k;
LL a[100005],pr[100005],dp[2][100005];
int nxt[202][100005];
LL sum(int l, int r)
{
	return pr[r] - pr[l - 1];
}

struct line
{
	int i;
	LL k, b;
	line(LL kk=0, LL bb=0,int ii=0)
	{
		k = kk;
		b = bb;
		i = ii;
	}
};

LL solve(line p, line q)
{
	return (q.b - p.b) / (p.k - q.k);
}


int main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		pr[i] = pr[i - 1] + a[i];
	}

	for (int z = 1; z <= k; z++)
	{
		int i = z % 2;
		int l = !i;
		vector<line> s;
		int ans=0;
		for (int j = n; j >= 1; j--)
		{
			line add = line(pr[j], dp[l][j + 1] - pr[j] * pr[j], j);
			while (s.size() > 1 && ((s[s.size() - 1].k == add.k && add.b >= s[s.size() - 1].b) || (s[s.size() - 1].k != add.k && solve(s[s.size() - 1], add) > solve(s[s.size() - 2], add))))
				s.pop_back();
			s.PB(add);

			ans = min(ans, (int)s.size() - 1);
			LL X = pr[n] + pr[j - 1];
			while (ans < s.size()-1 && s[ans].k*X + s[ans].b <= s[ans + 1].k*X + s[ans + 1].b)
				ans++;
			dp[i][j] = s[ans].k*X + s[ans].b - pr[j - 1] * pr[n];
			nxt[z][j] = s[ans].i;
		}
	}

	cout << dp[k%2][1] << endl;
	for (int i = k,l=1; i >= 1; i--)
	{
		cout << nxt[i][l] << " ";
		l = nxt[i][l] + 1;
	}
	cout << endl;
	return 0;
}

/*

3 1
2 1 2


40 3
7 5 7 5 1 2 3 4 6 7 8 2 1 2 3 4 6 7 8 2 7 7 5 1 2 3 4 6 7 8 2 5 1 2 3 4 6 7 8 2 

7 3
4 1 3 4 0 2 3 


*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (ans < s.size()-1 && s[ans].k*X + s[ans].b <= s[ans + 1].k*X + s[ans + 1].b)
           ~~~~^~~~~~~~~~~~

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