#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
typedef long long ll;
ll s[1000010],d[1000010],p[1000010],p2[1000010];
deque<ll> a,b;
void push(ll n,ll m){
int sz=a.size();
while( sz>1 && (b[sz-1]-b[sz-2])*(a[sz-1]-n) >= (m-b[sz-1])*(a[sz-2]-a[sz-1]) ){
sz--;
a.pop_back();
b.pop_back();
}
a.push_back(n);
b.push_back(m);
}
ll query(ll x){
int sz=a.size();
while( sz>1 && (b[1]-b[0]) <= x*(a[0]-a[1]) ){
sz--;
a.pop_front();
b.pop_front();
}
return a[0]*x+b[0];
}
int main(){
ll n,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>s[i];
p[i]=p[i-1]+s[i];
p2[i]=p2[i-1]+i*s[i];
}
push(-1,-p2[1]+p[1]);
for(ll i=1;i<=n;i++){
d[i]=p2[i];
/*for(ll j=0;j<i;j++){
d[i]=max(d[i], -(j+1)*p[i] +d[j]-p2[j+1]+(j+1)*p[j+1] +p2[i] );
}*/
d[i]=max(d[i],query(p[i])+p2[i]);
push(-(i+1),d[i]-p2[i+1]+(i+1)*p[i+1]);
}
cout<<d[n];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
32972 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
32972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
