/*
#include<stdio.h>
#include<algorithm>
#include<vector>
#pragma warning(disable:4996)
#define MN 1000000
#define INF 1e12
#define mp make_pair
#define cs (convex.size())
typedef long long ll;
using namespace std;
int N;
int inp[MN];
ll A[MN+1];
ll S[MN+1];
ll D[MN+1];
typedef pair<double,double> pf;
vector<pf> convex;
double bsearch(double x){
int l=0,m,r=cs-2;
int p;
while(l<=r){
m=(l+r)>>1;
double x0=convex[m+1].first,x1=convex[m].first;
double y0=convex[m+1].second,y1=convex[m].second;
if(x0<=x && x<=x1){
return ((x1-x)*y0+(x-x0)*y1)/(x1-x0);
}
if(x<x0){
l=m+1;
}
else{
r=m-1;
}
}
}
int main(){
// freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
scanf("%d",&N);
for(int i=0;i<N;i++)scanf("%d",&inp[i]);
for(int i=N-1;i>=0;i--)A[i]=(i==N-1)?inp[N-1]:(A[i+1]+inp[i]);
for(int i=N-1;i>=0;i--)S[i]=(i==N-1)?A[N-1]:(S[i+1]+A[i]);
convex.push_back(mp(INF,S[0]));
convex.push_back(mp(-INF,S[0]));
D[0]=max(inp[0],0);
for(int i=1;i<N;i++){
// D[i-1]+S[i]-x*i
double x0=convex[cs-1].first,y0=convex[cs-1].second;
convex.pop_back();
while(true){
double x1=convex[cs-1].first;
double y1=convex[cs-1].second;
double x=((x1-x0)*(S[i]+D[i-1]-y0)+x0*(y1-y0))/((y1-y0)+i*(x1-x0));
if(x<x1){
convex.push_back(mp(x,((x1-x)*y0+(x-x0)*y1)/(x1-x0)));
convex.push_back(mp(-INF,S[i]+D[i-1]+INF*i));
break;
}
else{
x0=x1,y0=y1;
convex.pop_back();
}
}
double v=bsearch(A[i+1])-S[i+1]-(i+1)*A[i+1];
D[i]=max((ll)(v+1e-7),D[i-1]);
}
printf("%lld\n",D[N-1]);
return 0;
}
//*/
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N = 1000005;
const double INF = 1.e15;
struct lineinfo {
long long slope,yadd;
double x_left,x_right;
lineinfo() {}
lineinfo(long long slope,long long yadd,double x_left,double x_right):
slope(slope),yadd(yadd),x_left(x_left),x_right(x_right) {}
};
int n;
long long inp[N],A[N],S[N],D[N];
vector<lineinfo> convex;
long long bsearch(long long x) {
int lo = 0,hi = (int)convex.size()-1,mid = -1;
while(lo <= hi) {
mid = (lo + hi)/2;
double x_left = convex[mid].x_left;
double x_right = convex[mid].x_right;
if(x_left <= x && x <= x_right) {
return
(long long)convex[mid].slope * x + convex[mid].yadd;
}
else {
if(x <= x_left) {
lo = mid+1;
}
else {
hi = mid-1;
}
}
}
}
int main(void) {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d",&n);
for(int i = 0; i < n; i++) {
scanf("%lld",&inp[i]);
}
A[n-1] = inp[n-1];
for(int i = n-2; i >= 0; i--) A[i] = A[i+1] + inp[i];
S[n-1] = A[n-1];
for(int i = n-2; i >= 0; i--) S[i] = S[i+1] + A[i];
if(n == 1) {
printf("%lld\n",max(inp[0],0ll));
return 0;
}
// input data processed
convex.push_back(lineinfo(0,S[0],-INF,INF));
D[0] = max(inp[0],0ll);
for(int i = 1; i < n; i++) {
long long a = -i,b = S[i] + (i >= 2)? D[i-2]: 0;
while((int)convex.size() > 0) {
long long c = convex.back().slope,d = convex.back().yadd;
double intersect_x = (double)(b-d)/(c-a);
if(convex.back().x_left <= intersect_x &&
intersect_x <= convex.back().x_right) {
convex.back().x_left = intersect_x;
convex.push_back(
lineinfo(a,b,-INF,intersect_x)
);
break;
}
convex.pop_back();
}
long long val = bsearch(A[i+1]) - S[i+1] - (i+1)*A[i+1];
D[i] = max(D[i-1],val);
}
long long ans = 0;
for(int i = 0; i < n; i++)
ans = max(ans,D[i]);
printf("%lld\n",ans);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
32460 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
32460 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
