Submission #100225

#	Time	Username	Problem	Language	Result	Execution time	Memory
100225		TadijaSebez	Split the sequence (APIO14_sequence)	C++11	33 / 100	2055 ms	84828 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define ldb long double
const int N=100050;
const int K=205;
const ll inf=1e18;
struct Line{ ll k,n;int id;Line(){}Line(ll a, ll b, int c):k(a),n(b),id(c){}pair<ll,int> Get(ll x){ return mp(k*x+n,id);}} Hull[N];
ldb sec(Line a, Line b){ return b.k==a.k?-1e18:(ldb)(a.n-b.n)/(b.k-a.k);}
int hsz,ptr=1;
ll dp[N],sum[N];
int go[N][K],a[N];
void Print(int n, int k)
{
	if(k==0) return;
	Print(go[n][k],k-1);
	printf("%i ",go[n][k]);
}
int main()
{
	int n,k;
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]),sum[i]=sum[i-1]+a[i];
	for(int j=1;j<=k;j++)
	{
		hsz=0;ptr=1;
		Hull[++hsz]=Line(sum[j],dp[j]-sum[j]*sum[j],j);
		for(int i=j+1;i<=n;i++)
		{
			Line l=Line(sum[i],dp[i]-sum[i]*sum[i],i);
			while(ptr<hsz && Hull[ptr].k*sum[i]+Hull[ptr].n<=Hull[ptr+1].k*sum[i]+Hull[ptr+1].n) ptr++;
			dp[i]=Hull[ptr].k*sum[i]+Hull[ptr].n;
			go[i][j]=Hull[ptr].id;
			while(hsz>ptr && (l.n-Hull[hsz].n)*(Hull[hsz].k-Hull[hsz-1].k)>=(Hull[hsz].n-Hull[hsz-1].n)) hsz--;
			//while(hsz>ptr && sec(Hull[hsz-1],Hull[hsz])>=sec(Hull[hsz],l)) hsz--;
			Hull[++hsz]=l;
		}
	}
	printf("%lld\n",dp[n]);
	Print(n,k);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:23: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:24: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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 0 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29