oj.uz

답안 #15240

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15240 2015-07-12T04:24:23 Z myungwoo 달리는 게임 (kriii3_E) C++14
70 / 70
 225 ms 40784 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 1000006
typedef long long lld;

const double eps = 1e-7;
int N;
int A[MAXN];
int stk[MAXN], scnt; double cp[MAXN];
lld D[MAXN], Nu[MAXN], S[MAXN];

inline lld get_y0(int i)
{ return D[i] - Nu[i] + S[i] * i; }

inline double cross_point(int a, int b)
{
	lld q1 = get_y0(a), q2 = get_y0(b);
	return (double)(q1 - q2) / (b - a);
}

int main()
{
	scanf("%d", &N);
	for (int i=1;i<=N;i++) scanf("%d", A+i);
	for (int i=1;i<=N;i++) Nu[i] = Nu[i-1] + (lld)i * A[i], S[i] = S[i-1] + A[i];
	lld ans = 0;
	stk[++scnt] = 0; cp[scnt] = -1e17;
	for (int i=1;i<=N;i++){
		int j = stk[upper_bound(cp+1, cp+scnt+1, -S[i] + eps) - cp - 1];
		D[i] = max(D[i-1], get_y0(j) - S[i] * j + Nu[i]);
		ans = max(ans, D[i]);

		while (scnt > 1 && cross_point(stk[scnt-1], i) < cp[scnt] + eps) scnt--;
		stk[++scnt] = i; cp[scnt] = cross_point(stk[scnt-1], i);
	}
	printf("%lld\n", ans);
}

Subtask #1
26.0 / 26.0

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

Subtask #2
44.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 40784 KB Output is correct
2 Correct 7 ms 40784 KB Output is correct
3 Correct 14 ms 40784 KB Output is correct
4 Correct 24 ms 40784 KB Output is correct
5 Correct 16 ms 40784 KB Output is correct
6 Correct 19 ms 40784 KB Output is correct
7 Correct 104 ms 40784 KB Output is correct
8 Correct 183 ms 40784 KB Output is correct
9 Correct 225 ms 40784 KB Output is correct