#include <bits/stdc++.h> #define ll long long #define ld long double #define f1(i,n) for(int i=1;i<=n;i++) #define __file_name "TEST" using namespace std; const ll maxn=1e6+5, inf=1e18; struct Line{ ll a, b; bool operator<(const Line &rhs) const{ return make_pair(a, -b) < make_pair(rhs.a, -rhs.b); } }; bool check(Line l1, Line l2, Line l3){ return 1.0L * (l2.b - l1.b) / (l2.a - l1.a) >= 1.0L * (l3.b - l2.b) / (l3.a - l2.a); } deque<Line> S; void addLine(Line l){ while(S.size() > 1){ if(check(S[S.size() - 2], S.back(), l)) S.pop_back(); else break; } S.push_back(l); } ll n, t[maxn], dp[maxn]; vector<ll> a; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(__file_name ".inp", "r")){ freopen(__file_name ".inp", "r", stdin); freopen(__file_name ".out", "w", stdout); } // code here cin >> n; f1(i,n) cin >> t[i]; t[n + 1] = inf; a.push_back(n + 1); for(int i = n; i >= 1; i--){ while(t[a.back()] <= t[i]){ a.pop_back(); } a.push_back(i); } reverse(a.begin(), a.end()); a.pop_back(); int sz = a.size(); a.insert(a.begin(), 0); // for(int i: a) cout << i << ' '; // cout << '\n'; f1(i,sz){ Line l1; l1.a = a[i]; l1.b = dp[i-1]; addLine(l1); ll val = -t[a[i]]; while(S.size() > 1){ Line la = S.front(); S.pop_front(); Line lb = S.front(); if(la.a * (val) + la.b < lb.a * (val) + lb.b){ S.push_front(la); break; } } dp[i] = (-val) * (n + 1) + S.front().a * (val) + S.front().b; } // cout << dp[2] << '\n'; cout << dp[sz]; return 0; }

Discharging.cpp: In function 'int main()':
Discharging.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(__file_name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(__file_name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~