#include<bits/stdc++.h> #pragma GCC optimize("unroll-loops,O3") using namespace std; using i64 = long long; #define int i64 #define vi vector<int> #define vvi vector<vi> #define vb vector<bool> #define se second #define fi first #define pii pair<int, int> #define sz(x) (int)(x).size() struct Line{ int m, c; Line(int m, int c) : m(m), c(c) {} Line() : Line(0, 0) {} inline int eval(int x){ return m * x + c; } inline long double x_int(Line &other){ return (long double)(other.c - c) / (m - other.m); } }; inline void solve(){ int n; cin >> n; vi t(n + 1), pfmax(n + 1); for(int i = 1; i <= n; i++){ cin >> t[i]; pfmax[i] = max(t[i], pfmax[i - 1]); // nondecreasing } deque<Line> dq; dq.emplace_back(0, 0); vi dp(n + 1); // dp[i] = ilk i kişi için olan grupları inceledim finale katkıları: dp[j] + (n - j) * pfmax[i], pfmax'ın o grupta olmadığı durum zaten optimal değil for(int i = 1; i <= n; i++){ while(sz(dq) >= 2 && dq.front().eval(pfmax[i]) >= dq[1].eval(pfmax[i])){ dq.pop_front(); } dp[i] = n * pfmax[i] + dq.front().eval(pfmax[i]); Line line = {-i, dp[i]}; while(sz(dq) >= 2 && line.x_int(dq.back()) <= dq.back().x_int(dq[sz(dq) - 2])){ dq.pop_back(); } dq.emplace_back(line); } cout << dp[n] << "\n"; return; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while(t--){ solve(); } return 0; }