This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
deque<pair<int, int> > dq;
int f(pair<int, int> x, int y){
return x.first*y + x.second;
}
long double intersect(int a, int b, int c, int d){
return (long double)(d-b)/(a-c);
}
void ins(int m , int c){
while(dq.size() > 1){
int s = dq.size();
if(intersect(dq.back().first, dq.back().second,m,c) <= intersect(dq[s-2].first, dq[s-2].second, m,c))dq.pop_back();
else break;
}
dq.push_back(make_pair(m,c));
}
int query(int x){
while(dq.size() > 1){
if(f(dq[0], x) <= f(dq[1], x))dq.pop_front();
// <= for max dp, >= for min dp
else break;
}
return f(dq[0], x);
}
int dp[1000005], A[1000005];
int Pmax[1000005];
main(){
ios::sync_with_stdio(0);cin.tie(0);
int n;cin >> n;
for(int i=1;i<=n;i++){
cin >> A[i];Pmax[i] = max(Pmax[i-1], A[i]);
}
dq.push_back(make_pair(0, 0));
for(int i=1;i<=n;i++){
int x = Pmax[i];
dp[i] = x*n - query(x);
ins(i, -dp[i]);
}
cout << dp[n];
}
Compilation message (stderr)
Discharging.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
30 | main(){
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |