Submission #87962

#	Time	Username	Problem	Language	Result	Execution time	Memory
87962		vanbang9710	Split the sequence (APIO14_sequence)	C++14	49 / 100	1029 ms	35352 KiB

sequence

#include<bits/stdc++.h>
#define P pair<lli, lli>
#define x first
#define y second
#define  mp make_pair
using namespace std;
typedef long long int lli;
const lli N=10009, K=209;
lli n, k, a[N], s[N], low[4*N], high[4*N], f[N][K], trace[N][K], leaf[N], maxnode=0;
struct T
{
	lli a, b, id;
};
struct T1
{
	lli x, a, b, id;
};
deque<T1> p;
T node[4*N];
void Built(lli v, lli l, lli h)
{
	maxnode=max(maxnode, v);
	low[v]=l;
	high[v]=h;
	if(l==h)
	{
		leaf[l]=v;
	}
	else
	{
		lli m=(l+h)/2;
		Built(v*2, l, m);
		Built(v*2+1, m+1, h);
	}
}
void Inp()
{
	cin>>n>>k;
	k++;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	Built(1, 1, n);
}
lli Get(T p, lli k)
{
	return p.a*k+p.b;
}
void Update(lli v, lli l, lli h, T val)
{
	if(l>h)
	{
		return ;
	}
	if(low[v]>h||high[v]<l)
	{
		return ;
	}
	if(low[v]>=l&&high[v]<=h)
	{
		if(Get(node[v], s[low[v]])>=Get(val, s[low[v]])&&Get(node[v], s[high[v]])>=Get(val, s[high[v]]))
		{
			return ;
		}
		if(Get(node[v], s[low[v]])<=Get(val, s[low[v]])&&Get(node[v], s[high[v]])<=Get(val, s[high[v]]))
		{
			node[v]=val;
			return ;
		}
		lli m=(low[v]+high[v])/2;
		if(Get(node[v], s[low[v]])>=Get(val, s[low[v]])&&Get(node[v], s[m])>=Get(val, s[m]))
		{
			Update(v*2+1, l, h, val);
			return ;
		}
		if(Get(node[v], s[low[v]])<=Get(val, s[low[v]])&&Get(node[v], s[m])<=Get(val, s[m]))
		{
			Update(v*2+1, l, h, node[v]);
			node[v]=val;
			return ;
		}
		if(Get(node[v], s[m+1])>=Get(val, s[m+1])&&Get(node[v], s[high[v]])>=Get(val, s[high[v]]))
		{
			Update(v*2, l, h, val);
			return ;
		}
		Update(v*2, l, h, node[v]);
		node[v]=val;
		return ;
	}
	Update(v*2, l, h, val);
	Update(v*2+1, l, h, val);
}
void Pre()
{
	for(int i=1;i<=maxnode;i++)
	{
		node[i]={0, 0, 0};
	}
	while(!p.empty())
	{
		T1 v=p.front();
		p.pop_front();
		Update(1, v.x, n, {v.a, v.b, v.id});
	}
}
P Max(lli k)
{
	lli v=leaf[k], maxx=-1, id;
	while(v)
	{
		if(maxx<Get(node[v], s[k]))
		{
			maxx=Get(node[v], s[k]);
			id=node[v].id;
		}
		v=v/2;
	}
	return mp(maxx, id);
}
void Solve()
{
	for(int i=1;i<=n;i++)
	{
		f[i][1]=0;
		p.push_back({i+1, s[i], -s[i]*s[i]+f[i][1], i});
	}
	for(int j=2;j<=k;j++)
	{
		Pre();
		for(int i=j;i<=n;i++)
		{
			P ans=Max(i);
			f[i][j]=ans.x;
			trace[i][j]=ans.y;
			p.push_back({i+1, s[i], -s[i]*s[i]+f[i][j], i});
		}
	}
	cout<<f[n][k]<<endl;
	lli x=n;
	for(int i=k;i>=2;i--)
	{
		cout<<trace[x][i]<<" ";
		x=trace[x][i];
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);
	Inp();
	Solve();
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> Max(lli)':
sequence.cpp:111:26: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
  lli v=leaf[k], maxx=-1, id;
                          ^~
sequence.cpp: In function 'void Solve()':
sequence.cpp:137:15: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
    trace[i][j]=ans.y;
               ^

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