| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 15481 |
2015-07-12T08:18:32 Z |
cki86201 |
달리는 게임 (kriii3_E) |
C++ |
|
236 ms |
44052 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
