Submission #100184

#	Time	Username	Problem	Language	Result	Execution time	Memory
100184		TadijaSebez	Split the sequence (APIO14_sequence)	C++11	0 / 100	52 ms	1536 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=100050;
int a[N];
ll sum[N];
int main()
{
	int n,k;
	vector<int> sp;
	scanf("%i %i",&n,&k);
	sp.push_back(0);
	sp.push_back(n);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),sum[i]=sum[i-1]+a[i];
	ll ans=0;
	while(k--)
	{
		ll mx=-1;
		int pos;
		for(int i=0;i+1<sp.size();i++)
		{
			for(int j=sp[i]+1;j<sp[i+1];j++)
			{
				ll val=(sum[j]-sum[sp[i]])*(sum[sp[i+1]]-sum[j]);
				if(val>mx) mx=val,pos=j;
			}
		}
		//printf("%i %lld\n",pos,mx);
		auto it=sp.begin();
		while(*it<pos) it++;
		sp.insert(it,pos);
		//for(int i=0;i<sp.size();i++) printf("%i ",sp[i]);printf("\n");
		ans+=mx;
	}
	printf("%lld\n",ans);
	for(int i=1;i+1<sp.size();i++) printf("%i ",sp[i]);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i+1<sp.size();i++)
               ~~~^~~~~~~~~~
sequence.cpp:36:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i+1<sp.size();i++) printf("%i ",sp[i]);
              ~~~^~~~~~~~~~
sequence.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:14:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]),sum[i]=sum[i-1]+a[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