oj.uz

답안 #14234

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
14234 2015-05-06T12:35:36 Z shuuna 수열 (APIO14_sequence) C++
0 / 100
 0 ms 88056 KB 
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 210
#define maxm 100010
using namespace std;
typedef long long LL;
struct Node
{
	LL S,G;
	int id;
	Node() {}
	Node(LL S,LL G,int id): S(S),G(G),id(id) {}
};
int pre[maxn][maxm],a[maxm],n,m;
LL sum[maxm],dp[maxm];
void read()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",a+i);
		sum[i]=sum[i-1]+a[i];
	}
}
void print(int n,int m)
{
	if(n==0)
		return ;
	print(n-1,pre[n][m]);
	printf("%d ",pre[n][m]);
}
void Dp()
{
	static Node queue[maxm];
	for(int i=1;i<=m;++i)
	{
		int front=1,rear=1;
		queue[rear]=Node(dp[i]-sum[i]*sum[i],sum[i],i);
		for(int j=i+1;j<=n;++j)
		{
			while(front<rear&&queue[front].S+sum[j]*queue[front].G<=queue[front+1].S+sum[j]*queue[front+1].G)
				++front;
			Node now(dp[j]-sum[j]*sum[j],sum[j],j);
			dp[j]=queue[front].S+sum[j]*queue[front].G;
			pre[i][j]=queue[front].id;
			while(front<rear&&(now.S-queue[rear].S)*(queue[rear].G-queue[rear-1].G)>=(queue[rear].S-queue[rear-1].S)*(now.G-queue[rear].G))
				--rear;
			queue[++rear]=now;
		}
	}
	cout<<dp[n]<<endl;
	print(m,n);
}
int main()
{
	//freopen("sequence.in","r",stdin);
	//freopen("sequence.out","w",stdout);
	read();
	Dp();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 88056 KB close (syscall #3) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Halted 0 ms 0 KB -