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;
typedef long long ll;
const int MAX_N=1e6+10;
const int MAX_P=MAX_N*4;
const int MAX=1e9;
ll val[MAX_N];
int tr[MAX_P];
ll ma[MAX_N];
ll n;
void maxi(){
int m=-1,id;
for(int i=0;i<n;i++){
if(m<val[i]){
m=val[i];
id=i;
}
ma[i]=id;
}
}
ll dp[MAX_N];
ll maxres(int l,int r){
if(dp[r]!=-1) return dp[r];
int i=ma[r];
if(i==0) return val[i]*n;
ll d=(n-i);
ll ans=val[i]*n;
for(int k=i-1;k>=0;k--){
ans=min(ans,val[i]*d+maxres(0,k));
d++;
}
return dp[r]=ans;
}
ll mdp[MAX_N];
int coste(int i,int x){
return x*(n+1)-i*x+mdp[i-1];
}
int time(int i,int j){
int l=0,r=1e6+10;
while(r-l>1){
int mid=(l+r)/2;
if(coste(i,mid)>=coste(j,mid)) r=mid;
else l=mid;
}
return r;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(dp,-1,sizeof dp);
cin>>n;
for(int i=0;i<n;i++){
int a; cin>>a;
val[i]=a;
}
mdp[0]=0;
deque<int> dq;
for(int i=1;i<=n;i++){
mdp[i]=1e9;
int t=dq.size();
while(t>=3 && time(dq[t-2],dq[t-1])>=time(dq[t-2],i)){
dq.pop_back(); t--;
}
dq.push_back(i);
while(dq.size()>=2 && coste(dq[0],val[i-1])>=coste(dq[1],val[i-1])){
dq.pop_front();
}
mdp[i]=coste(dq.front(),val[i-1]);
}
cout<<mdp[n]<<endl;
}
Compilation message (stderr)
Discharging.cpp: In function 'void maxi()':
Discharging.cpp:18:11: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
18 | ma[i]=id;
| ^~
# | 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... |