Submission #92747

#	Time	Username	Problem	Language	Result	Execution time	Memory
92747		davitmarg	Split the sequence (APIO14_sequence)	C++17	11 / 100	136 ms	24656 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,st;
	LL a[100005],pr[100005],dp[202][10004];
	int nxt[202][10004];
	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)
	{
		if ((p.k - q.k) == 0)
			return mod * mod;
		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 i = 1; i <= k; i++)
		{
			vector<line> s;
			int ans=0;
			for (int j = n; j >= 1; j--)
			{
				line add = line(pr[j], dp[i - 1][j + 1] - pr[j] * pr[j], j);
				while (s.size() >= 2 && ((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);
				if (n - j >= i - 1)
				{
					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[i][j] = s[ans].i;
				}
			}
		}

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

	/*

	9 3
	2 2 2 2 2 2 2 2 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:78:17: 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: 0 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29