답안 #15481

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
15481	2015-07-12T08:18:32 Z	cki86201	달리는 게임 (kriii3_E)	C++	70 / 70	236 ms	44052 KB

E

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<set>
#include<algorithm>

typedef long long ll;
typedef std::pair<ll, ll> pl;
#define X first
#define Y second

const int MX = 1000010;

int n, a[MX];
ll s[MX], ss[MX];
ll d[MX];
struct lines{
	pl p[MX];
	int f;
	void init(){ f = 0; }
	void push(pl x){
		while (f>1 && (double)(p[f - 1].X - p[f - 2].X) * (x.Y - p[f - 1].Y) <= (double)(x.X - p[f - 1].X) * (p[f - 1].Y - p[f - 2].Y))--f;
		p[f++] = x;
	}
	ll get(ll x){
		ll ret = 0;
		int low = 0, high = f - 2, mid;
		while (low <= high){
			mid = (low + high) >> 1;
			double inter = (double)(p[mid + 1].Y - p[mid].Y) / (p[mid].X - p[mid + 1].X);
			if (inter > x)low = mid + 1, ret = std::max(ret, p[mid + 1].X * x + p[mid + 1].Y);
			else high = mid - 1, ret = std::max(ret, p[mid].X * x + p[mid].Y);
		}
		return ret;
	}
}Lin;

int main(){
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", a + i);
	for (int i = 1; i <= n; i++)s[i] = s[i - 1] + a[i];
	for (int i = 1; i <= n; i++)ss[i] = ss[i - 1] + s[i];
	Lin.init();
	Lin.push(pl(0, 0));
	for (int i = 1; i <= n; i++){
		d[i] = Lin.get(s[i]) + s[i] * i - ss[i-1];
		if (d[i] < d[i - 1])d[i] = d[i - 1];
		Lin.push(pl(-i, d[i] + ss[i - 1]));
		//printf("%d : %d\n", i, d[i]);
	}
	printf("%lld", d[n]);
	return 0;
}

Subtask #1

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	44052 KB	Output is correct
2	Correct	0 ms	44052 KB	Output is correct
3	Correct	0 ms	44052 KB	Output is correct
4	Correct	0 ms	44052 KB	Output is correct
5	Correct	0 ms	44052 KB	Output is correct
6	Correct	5 ms	44052 KB	Output is correct
7	Correct	5 ms	44052 KB	Output is correct
8	Correct	0 ms	44052 KB	Output is correct
9	Correct	0 ms	44052 KB	Output is correct
10	Correct	0 ms	44052 KB	Output is correct
11	Correct	0 ms	44052 KB	Output is correct
12	Correct	0 ms	44052 KB	Output is correct
13	Correct	2 ms	44052 KB	Output is correct
14	Correct	5 ms	44052 KB	Output is correct
15	Correct	5 ms	44052 KB	Output is correct
16	Correct	2 ms	44052 KB	Output is correct
17	Correct	5 ms	44052 KB	Output is correct
18	Correct	5 ms	44052 KB	Output is correct

Subtask #2

44.0 / 44.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	44052 KB	Output is correct
2	Correct	18 ms	44052 KB	Output is correct
3	Correct	14 ms	44052 KB	Output is correct
4	Correct	24 ms	44052 KB	Output is correct
5	Correct	22 ms	44052 KB	Output is correct
6	Correct	25 ms	44052 KB	Output is correct
7	Correct	119 ms	44052 KB	Output is correct
8	Correct	236 ms	44052 KB	Output is correct
9	Correct	232 ms	44052 KB	Output is correct