Submission #94857

#	Time	Username	Problem	Language	Result	Execution time	Memory
94857		aminra	Split the sequence (APIO14_sequence)	C++14	100 / 100	667 ms	84224 KiB

sequence

//Smaug never desolated!!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = (int)1e5 + 3;
const int MAXS = (int)203;
const int MOD = (int)1e9 + 7;
const int infint = (int)1e9;
const ll inf = (ll)1e15;
int n, k;
ll dp[2][MAXN];
int par[MAXS][MAXN];
ll part[MAXN];
int a[MAXN];
pair<ll, ll> D[100005];
ld calc(pair<ll, ll> a, pair<ll, ll> b) 
{
	return ((ld)a.second - b.second) / (b.first - a.first);
}
int main() 
{
	scanf("%d%d", &n, &k);
	set<int> s;
	for (int i = 1; i <= n; i++) 
	{
		scanf("%d", &a[i]);
		part[i] = part[i - 1] + a[i];
		if(!a[i])
			s.insert(i);
	}
	for (int i = 1; i <= k; i++) 
	{
		deque<int> dq;
		int cur = i & 1;
		int pre = (i - 1) & 1;
		for (int j = 1; j <= n; j++) 
		{
			if (!a[j]) 
			{
				dp[cur][j] = dp[cur][j - 1];
				par[i][j] = par[i][j - 1];
				continue;
			}
			while (dq.size() > 1 && calc(D[dq[0]], D[dq[1]]) <= part[j])
				dq.pop_front();
			if (!dq.empty()) 
			{
				dp[cur][j] = D[dq[0]].first * part[j] + D[dq[0]].second;
				par[i][j] = dq[0];
			}
			ll a = part[j];
			ll b = dp[pre][j] - part[j] * part[j];
			D[j] = make_pair(a, b);
			while (dq.size() > 1 && calc(D[dq.back()], D[j]) <= calc(D[dq[dq.size() - 2]], D[j]))
				dq.pop_back();
			dq.push_back(j);
		}
	}
	printf("%lld\n", dp[k & 1][n]);
	vector<int> ans;
	while (k) 
	{
		ans.push_back(par[k][n]);
		n = par[k][n];
		k--;
	}
	for (int i = 0; i < ans.size(); i++) 
	{
		s.erase(ans[i]);
		if (!ans[i]) 
		{
			printf("%d ", *s.begin());
			s.erase(s.begin());
		}
		else
			printf("%d ", ans[i]);
	}
	printf("\n");
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) 
                  ~~^~~~~~~~~~~~
sequence.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[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