#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
28552 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
28552 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
