Submission #521966

#TimeUsernameProblemLanguageResultExecution timeMemory
521966DanerZeinDischarging (NOI20_discharging)C++14
47 / 100
1091 ms54504 KiB
#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; } } int unir(int a,int b){ if(a==n || b==n){ if(a==n) return b; if(b==n) return a; return n; } if(val[a]>val[b]) return a; else{ if(val[a]==val[b]) return min(a,b); else return b; } } void init(int node,int a,int b){ if(a==b){ tr[node]=a; return; } int mid=(a+b)/2,le=2*node+1,ri=2*node+2; init(le,a,mid); init(ri,mid+1,b); tr[node]=unir(tr[le],tr[ri]); } ll query(int node,int a,int b,int l,int r){ if(b<l || a>r) return n; if(l<=a && r>=b) return tr[node]; int mid=(a+b)/2,le=2*node+1,ri=2*node+2; return unir(query(le,a,mid,l,r),query(ri,mid+1,b,l,r)); } 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(); val[n]=-MAX; // init(0,0,n-1); cout<<maxres(0,n-1)<<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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...