fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define fi first
  5. #define se second
  6.  
  7. using ll = long long;
  8.  
  9. const int N = 1e6 + 7;
  10.  
  11. int n;
  12. ll a[N], dp[N];
  13.  
  14. struct Line{
  15.     ll m, b;
  16.     ll get(ll x){
  17.         return m * x + b;
  18.     }
  19. };
  20.  
  21. bool bad(Line l1, Line l2, Line l3){
  22.     return (__int128)(l2.b - l1.b) * (l2.m - l3.m)
  23.          >= (__int128)(l3.b - l2.b) * (l1.m - l2.m);
  24. }
  25.  
  26. int main(){
  27.     faster;
  28.  
  29.     cin >> n;
  30.     for(int i = 1; i <= n; i++){
  31.         cin >> a[i];
  32.         a[i] = max(a[i], a[i-1]);
  33.     }
  34.  
  35.     deque<Line> dq;
  36.     dq.push_back({0, 0});
  37.  
  38.     for(int i = 1; i <= n; i++){
  39.         ll x = a[i];
  40.  
  41.         while(dq.size() >= 2 && dq[0].get(x) >= dq[1].get(x))
  42.             dq.pop_front();
  43.  
  44.         dp[i] = dq.front().get(x) + n * x;
  45.  
  46.         Line cur = {-i, dp[i]};
  47.  
  48.         while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), cur))
  49.             dq.pop_back();
  50.  
  51.         dq.push_back(cur);
  52.     }
  53.  
  54.     cout << dp[n];
  55. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/y2AGQC
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!