# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
521967 | DanerZein | Discharging (NOI20_discharging) | C++14 | 1085 ms | 54428 KiB |
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;
}
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;
}
maxi();
cout<<maxres(0,n-1)<<endl;
}
Compilation message (stderr)
# | 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... |