Submission #112666

#	Time	Username	Problem	Language	Result	Execution time	Memory
112666		nafis_shifat	Split the sequence (APIO14_sequence)	C++14	39 / 100	2047 ms	24064 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;	
	return (cumsum[res]-cumsum[l-1])*(cumsum[r]-cumsum[res]);	
	
}


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;i++)
	    {
	        for(int l=i;l<n;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--)
	{
	    cout<<hld[l][i]<<" ";
	    l=hld[l][i]+1;
	    
	}
	
}

Compilation message (stderr)

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

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