#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int mn = 1e6 + 5; ll n, a[mn]; struct line{ ll m, b; ld x; line(ll m_ = 0, ll b_ = 0, ld x_ = -1e30){ m = m_; b = b_; x = x_; } }; ld intersect(const line &l1, const line &l2){ return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m); } struct node{ ll val, l, r; }; vector<node> v; struct convexhulltrick{ deque<line> hull; void add_line(ll m, ll b){ line cur(m, b); if(!hull.empty() && hull.back().m == m){ if(hull.back().b <= b) return; hull.pop_back(); } while(!hull.empty()){ ld ix = intersect(hull.back(), cur); if(ix <= hull.back().x) hull.pop_back(); else{ cur.x = ix; break; } } hull.push_back(cur); } ll query(ll x){ while(hull.size() >= 2 && hull[1].x <= (ld)x) hull.pop_front(); line l = hull.front(); // cout << l.m << " " << l.b << "*\n"; return l.m * x + l.b; } }; void solve(){ cin >> n; for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i <= n; ++i){ if(v.empty() || v.back().val < a[i]) v.push_back({a[i], i, i}); else ++v.back().r; } convexhulltrick cht; cht.add_line(0, 0); ll ans; for(auto i : v){ // cout << i.val << " " << i.r << "\n"; ll dp = cht.query(i.val) + i.val * n; //// cout << dp << "\n"; ans = dp; cht.add_line(-i.r, dp); } cout << ans; return; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); if(fopen(".INP", "r")) { freopen(".INP", "r", stdin); freopen(".OUT", "w", stdout); } int testCase = 1; //cin >> testCase; while(testCase--) solve(); }

Discharging.cpp: In function 'int main()':
Discharging.cpp:79:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |                 freopen(".INP", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~
Discharging.cpp:80:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |                 freopen(".OUT", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~