oj.uz

답안 #13136

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13136 2015-01-31T16:22:40 Z choyi0521 수열 (APIO14_sequence) C++
0 / 100
 0 ms 91708 KB 
#include<stdio.h>
#define MaxN 100001
typedef long long int lint;
typedef struct Line{
	lint m;
	lint b;
	int from;
	Line(){m=b=from=0;}
	Line(lint _m,lint _b,int _from){m=_m;b=_b;from=_from;}
}line;
line l[MaxN];
int ans[220][MaxN],p,sz;
int n,c;
lint sum[MaxN],dy1[MaxN],dy2[MaxN];
double cross(line i,line j){return (double)(i.b-j.b)/(j.m-i.m);}
void push(line t){
	while(sz>=2 && cross(t,l[sz])<cross(l[sz-1],l[sz])) sz--;
	l[++sz]=t;
}
int main(){
	int i,j;
	scanf("%d %d",&n,&c);
	for(i=1; i<=n; i++){
		scanf("%d",&sum[i]);
		sum[i]+=sum[i-1];
	}
	p=1;
	push(Line(0,0,0));
	for(i=1; i<=c; i++){
		for(j=i; j<n; j++){
			while(sz-p>=1 && cross(l[p],l[p+1])<=sum[j]) p++;
			dy2[j]= l[p].m*sum[j]+l[p].b + sum[j]*(sum[n]-sum[j]);
			ans[i][j]=l[p].from;
		}
		p=1;
		sz=0;
		for(j=i; j<n; j++){
			dy1[j]=dy2[j];
			push(Line(sum[j],-sum[n]*sum[j]+dy1[j],j));
		}
	}
	lint max_=0;
	int pos,p[220],pcnt=0;
	for(i=1; i<=n; i++){
		if(max_<dy1[i]){
			max_=dy1[i];
			pos=i;
		}
	}
	while(pos!=0){
		p[++pcnt]=pos;
		pos=ans[c-pcnt+1][pos];
	}
	printf("%lld\n",max_);
	for(i=pcnt; i>=1; i--){
		printf("%d ",p[i]);
	}
	return 0;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 91708 KB Output is correct - contestant found the optimal answer: 108 == 108
2 Correct 0 ms 91708 KB Output is correct - contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 91708 KB Output isn't correct - Integer 4194992 violates the range [1, 1]
4 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 -