oj.uz

Submission #23389

# Submission time Handle Problem Language Result Execution time Memory
23389 2017-05-08T17:38:31 Z petrpan Split the sequence (APIO14_sequence) C++14
0 / 100
 0 ms 1844 KB 
#include <iostream>
#include <algorithm>

using namespace std;

long long n,a[100010],f[210][100010],b[100010],num,k;

struct ioi2
{
	long long a,b;
}it[210][400010];

long long get(ioi2 p ,long long x)
{
	return (p.a*x+p.b);
}

void update(int tr,int p,int l,int r,ioi2 x)
{
	ioi2 y=it[tr][p];
	if (r<l) return;
	int m=(l+r)/2;
	if (get(x,b[l])>=get(y,b[l]) and get(x,b[r])>=get(y,b[r]))
	{
		it[tr][p]=x;
		return;
	}
	if (get(x,b[l])<=get(y,b[l]) and get(x,b[r])<=get(y,b[r]))
		return;
	if (get(x,b[m])>=get(y,b[m]) and get(x,b[l])>=get(y,b[l]))
	{
		update(tr,p*2+1,m+1,r,it[tr][p]);
		it[tr][p]=x;
		return;
	}
	if (get(x,b[m])<=get(y,b[m]) and get(x,b[l])<=get(y,b[l]))
	{
		update(tr,p*2+1,m+1,r,x);
		return;
	}
	if (get(x,b[m+1])>=get(y,b[m+1]) and get(x,b[r])>=get(y,b[r]))
	{
		update(tr,p*2,l,m,it[tr][p]);
		it[tr][p]=x;
		return;
	}
	if (get(x,b[m+1])<=get(y,b[m+1]) and get(x,b[r])<=get(y,b[r]))
	{
		update(tr,p*2,l,m,x);
		return;
	}
}	

long long query(int tr,int p,int l,int r,int x)
{
	if (x<l or x>r) return 0;
	if (l==r) return get(it[tr][p],b[x]);
	long long res=get(it[tr][p],b[x]);
	return res=max(res,max(query(tr,p*2,l,(l+r)/2,x),query(tr,p*2+1,(l+r)/2+1,r,x)));
}

int main()
{	
	cin >> n >> k;
	for (int i=1;i<=n;i++)
		cin >> a[i],a[i]+=a[i-1],b[i]=a[i];
	sort(b+1,b+n+1);
	num=unique(b+1,b+n+1)-b-1;
	/*
	for (int i=1;i<=k+1;i++)
		for (int j=1;j<=n;j++)
	{
		if (i==1) f[i][j]=0;
		else
		{
			ioi2 tp;
			tp.a=-a[j];
			tp.b=f[i-1][j]-a[j]*a[j];
			int pos=lower_bound(b+1,b+num+1,a[j])-b;
			update(i-1,1,1,num,tp);
			f[i][j]=query(i-1,1,1,num,pos);
		}
	}*/
	for (int i=1;i<=n;i++)
		f[0][i]=-1e18;
	for (int i=1;i<=k+1;i++)
		for (int j=0;j<=n;j++)
		{
			for (int k=1;k<j;k++)
				f[i][j]=max(f[i][j],f[i-1][k]+(a[j]-a[k])*a[k]);
		}
	cout << f[k+1][n];
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1844 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -