Submission #112486

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

sequence

#include<bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> v;
ll cumsum[100008];
int mtg=-1;
int 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];
		
	}
	
	set< pair<int,int> > segs;
	segs.insert({1,n});
	ll res=0;
	vector<int> fn;
	while(k--)
	{
		set<pair<int,int> >::iterator it=segs.begin();
		
		int curr=bs(it->first,it->second);
		int cl=it->first;
		int cr=it->second;
		
		int k=mtg;
		it++;
		for(;it!=segs.end();it++)
		{
			int tmp=bs(it->first,it->second);
			if(tmp>curr)
			{
				curr=tmp;
				cl=it->first;
				cr=it->second;
				k=mtg;
			}						
		}	
		res+=curr;
		segs.insert({cl,k});
		segs.insert({k+1,cr});
		segs.erase({cl,cr});
		
		fn.push_back(k);
					
	}
	cout<<res<<endl;
	for(int i=0;i<fn.size();i++)cout<<fn[i]<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<fn.size();i++)cout<<fn[i]<<" ";
              ~^~~~~~~~~~

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