Submission #112683

#	Time	Username	Problem	Language	Result	Execution time	Memory
112683		nafis_shifat	Split the sequence (APIO14_sequence)	C++14	0 / 100	2060 ms	24056 KiB

sequence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> v;
ll cumsum[100008];
int mtg=-1;
ll bs(int l,int r)
{
	int lo=l;
	int hi=r;
	int res=0;
	while(lo<=hi)
	{
		int mid=(lo+hi)/2;
	    
	    int a=cumsum[mid]-cumsum[l-1];
	    int b=cumsum[r]-cumsum[mid-1];
	    if(a>b)
	    {
	    	hi=mid-1;
	    	
		}
		else 
		{
			res=mid;
			lo=mid+1;
		}
		
	}
	mtg=res;	
	ll f= (cumsum[res]-cumsum[l-1])*(cumsum[r]-cumsum[res]);
	if(f==0)mtg=0;
	return f;
}


int main()
{
	int n,k;
	cin>>n>>k;
	
	ll a[n+1];
	cumsum[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cumsum[i]=cumsum[i-1]+a[i];
		
	}
	ll dp[n+1][k+1]={};
	int hld[n+1][k+1]={};
	int next[n+1][k+1];

	for(int i=1;i<n;i++)
	{
	    dp[i][1]=bs(i,n);
	    hld[i][1]=mtg;
	    
	}
	
	for(int j=2;j<=k;j++)
	{
	    for(int i=1;i<=n-j;i++)
	    {
	        for(int l=i;l<=n-j;l++)
	        {
	            ll tmp=(cumsum[l]-cumsum[i-1])*(cumsum[n]-cumsum[l])+dp[l+1][j-1] ;
	            if(tmp  >  dp[i][j])
	            {
	                
	                dp[i][j]=tmp;
	                
	                hld[i][j]=l;
	                
	            }
	        }
	    }
	}
	
	cout<<dp[1][k]<<endl;;
	int l=1;

	for(int i=k;i>0;i--)
	{
	    int t=hld[l][i];
	    if(t==0 || t<=l)
	    {
	        cout<<++l<<" ";
	        
	    }
	    else
	    {
	        cout<<t<<" ";
	        l=hld[l][i]+1;
	    }
	    
	    
	}
	
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:52:6: warning: unused variable 'next' [-Wunused-variable]
  int next[n+1][k+1];
      ^~~~

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