Submission #137935

#	Time	Username	Problem	Language	Result	Execution time	Memory
137935		mahmoudbadawy	Split the sequence (APIO14_sequence)	C++17	0 / 100	276 ms	18780 KiB

sequence

#include <bits/stdc++.h>

using namespace std;

struct line
{
	long long m,c;
	double x;
	int ind;
	int isq;
	line():m(0),c(0),isq(0),x(0),ind(0){}
	line(long long m,long long c,int ind):m(m),c(c),isq(0),x(0),ind(ind){}
	bool operator<(const line &other) const
	{
		if(isq||other.isq) return x<other.x;
		if(m==other.m) return ind<other.ind;
		return m<other.m;
	}
};

struct convex_hull
{
	set<line> ss;
	set<line>::iterator prev(set<line>::iterator it)
	{
		return --it;
	}
	set<line>::iterator next(set<line>::iterator it)
	{
		return ++it;
	}
	bool hasprev(set<line>::iterator it)
	{
		return (it!=ss.end()&&it!=ss.begin());
	}

	bool hasnext(set<line>::iterator it)
	{
		return (it!=ss.end()&&next(it)!=ss.end());
	}

	double intersect(line a,line b)
	{
		if(a.m==b.m)
			return (1LL<<50);
		return (1.0*(a.c-b.c))/(b.m-a.m);
	}

	bool isbad(line a,line b,line c)
	{
		return intersect(b,c)<intersect(b,a);
	}

	bool isbad(set<line>::iterator it)
	{
		return hasnext(it)&&hasprev(it)&&isbad(*prev(it),*it,*next(it));
	}

	set<line>::iterator update(set<line>::iterator it)
	{
		double x=(hasnext(it)?intersect(*it,*next(it)):(1LL<<50));
		line cur=*it;
		cur.x=x;
		ss.erase(it);
		it=ss.insert(cur).first;
		return it;
	}

	void addline(long long m,long long c,int ind)
	{
		set<line>::iterator it=ss.insert({m,c,ind}).first;
		if(isbad(it))
		{
			ss.erase(it);
			return;
		}
		while(hasnext(it)&&isbad(next(it))) ss.erase(next(it));
		while(hasprev(it)&&isbad(prev(it))) ss.erase(prev(it));
		it=update(it);
		if(hasnext(it)) update(next(it));
		if(hasprev(it)) update(prev(it));
	}

	pair<long long,int> query(long long x)
	{
		line q;
		q.x=x; q.isq=1;
		set<line>::iterator it=ss.lower_bound(q);
		if(it==ss.end())
			return {(1LL<<50),-1};
		return {((*it).m)*x+((*it).c),(*it).ind};
	}
};

convex_hull ss[2];
int n,k;
int arr[100005];
long long sum[100005];
long long mem[201][100005];
int sp[201][100005];

int main()
{
	int st=1,t=1;
	//scanf("%d %d",&st,&t);
	while(t--)
	{
		scanf("%d %d",&n,&k);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&arr[i]);
			sum[i]=arr[i];
			sum[i]+=sum[i-1];
		}
		for(int i=0;i<=k;i++)
		{
			mem[i][n+1]=0;
		}
		ss[0].ss.clear(); ss[1].ss.clear();
		for(int j=k;j>=0;j--)
		{
			for(int i=n;i>=j+1;i--)
			{
				mem[j][i]=mem[j][i+1];
				if(j==k)
				{
					ss[j%2].addline(sum[i-1],mem[j][i],i);
					sp[j][i]=n+1;
					continue;
				}
				/*for(int l=i+1;l<=n+1;l++)
				{
					mem[i][j]=max(mem[i][j],(sum[l-1]-sum[i-1])*(sum[i-1])+mem[l][j+1]);
					mem[i][j]=sum[l-1]*sum[i-1]-sum[i-1]*sum[i-1]+mem[l][j+1];
				}*/
				pair<long long,int> x=ss[1-j%2].query(sum[i-1]);
				mem[j][i]=max(mem[j][i],x.first-sum[i-1]*sum[i-1]);
				sp[j][i]=x.second;
				//cout << i << " " << j << " " << mem[i][j] << query(j+1,sum[i-1]) << endl;
				ss[j%2].addline(sum[i-1],mem[j][i],i);
			}
			ss[1-j%2].ss.clear();
			ss[j%2].addline(sum[n],0,n+1);
		}
		cout << mem[0][1] << endl;
		int x=1;
		for(int i=0;i<k;i++)
		{
			cout << sp[i][x]-1 << " \n"[i==k-1];
			x=sp[i][x];
			//for(int j=1;j<=n;j++)
			//	cout << sp[i][j] << " \n"[j==n];
		}
	}
}

Compilation message (stderr)

sequence.cpp: In constructor 'line::line()':
sequence.cpp:10:6: warning: 'line::isq' will be initialized after [-Wreorder]
  int isq;
      ^~~
sequence.cpp:8:9: warning:   'double line::x' [-Wreorder]
  double x;
         ^
sequence.cpp:11:2: warning:   when initialized here [-Wreorder]
  line():m(0),c(0),isq(0),x(0),ind(0){}
  ^~~~
sequence.cpp: In constructor 'line::line(long long int, long long int, int)':
sequence.cpp:10:6: warning: 'line::isq' will be initialized after [-Wreorder]
  int isq;
      ^~~
sequence.cpp:8:9: warning:   'double line::x' [-Wreorder]
  double x;
         ^
sequence.cpp:12:2: warning:   when initialized here [-Wreorder]
  line(long long m,long long c,int ind):m(m),c(c),isq(0),x(0),ind(ind){}
  ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:104:6: warning: unused variable 'st' [-Wunused-variable]
  int st=1,t=1;
      ^~
sequence.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&k);
   ~~~~~^~~~~~~~~~~~~~~
sequence.cpp:111:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&arr[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