Submission #172934

#	Time	Username	Problem	Language	Result	Execution time	Memory
172934		RafaelSus	Split the sequence (APIO14_sequence)	C++14	71 / 100	2053 ms	84964 KiB

sequence

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int mxn=1e5+2;
 
vector<ll> m;
vector<ll> b;
vector<int> idx;
int ptr=0;
int path[mxn][202]={};
ll dp[mxn+10][2]={};
 
	
ll a[mxn+5]={};
ll s[mxn+5]={};
 
 
void print(int st,int k)
{
    if(path[st][k]==0)
    {
        cout<<st<<" ";
        
        return;
    }
    print(path[st][k],k-1);
    cout<<st<<" ";
   
}
bool bad(int f1,int f2,int f3)
{
	return (b[f3]-b[f1])*(m[f1]-m[f2])>=(b[f2]-b[f1])*(m[f1]-m[f3]);
}
 
void add(ll m_,ll b_,int id)
{
   
    
	m.push_back(m_);
	b.push_back(b_);
	idx.push_back(id);
	int sz=m.size();
	while(sz>=3 && bad(sz-3,sz-2,sz-1))
	{
		m.erase(m.end()-2);
		b.erase(b.end()-2);
		idx.erase(idx.end()-2);
		sz--;
	}
}
 
ll func(int p,ll x)
{
	return m[p]*x+b[p];
}
 
pair<ll,int> query(ll x)
{
	if(ptr>=m.size())ptr=m.size()-1;
	while(ptr+1<m.size() && func(ptr,x)<=func(ptr+1,x))ptr++;
 
	return {func(ptr,x),idx[ptr]};
}
 
 
 
int main()
{
	
	int n,k;
	cin>>n>>k;
	
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	
	
 
 
	for(int i=1;i<=n;i++)
	{
	    
	    dp[i][1]=s[i]*(s[n]-s[i]);
	    path[i][1]=0;
	    //add(-s[i],dp[i][1]);
 
	}
 
	for(int i=2;i<=k;i++)
	{
		m.clear();
		b.clear();
		idx.clear();
		int v=(i-1)%2;
		ptr=0;
		add(0,0,0);
		
	
	
	
		for(int j=1;j<=n;j++)
		{
			
			if(j<i )
			{
			    if(j==i-1)
			     add(-s[j],dp[j][v],j);
			    continue;
 
			}
		
		
			pair<ll,int> pd=query(s[n]-s[j]);
		
		
		
			dp[j][v^1]=pd.first+s[n]*s[j]-s[j]*s[j];
			path[j][i]=pd.second;
		
		    add(-s[j],dp[j][v],j);
		   
 
 
		}
		
	}
 
	ll mx=0,st=1;
	for(int i=1;i<n;i++)
	{
	    if(dp[i][k%2]>=mx)
	    {
	        mx=dp[i][k%2];
	        st=i;
	    }
	}
 
	cout<<mx<<endl;
	print(st,k);
	
	
 
 
 
	
 
 
}

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, int> query(long long int)':
sequence.cpp:60:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(ptr>=m.size())ptr=m.size()-1;
     ~~~^~~~~~~~~~
sequence.cpp:61:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr+1<m.size() && func(ptr,x)<=func(ptr+1,x))ptr++;
        ~~~~~^~~~~~~~~

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