Submission #521952

#TimeUsernameProblemLanguageResultExecution timeMemory
521952DanerZeinDischarging (NOI20_discharging)C++14
11 / 100
409 ms21056 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 n; 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 maxres(int l,int r){ int i=query(0,0,n-1,l,r); if(i==0) return val[i]*n; ll d=(n-i); int j=query(0,0,n-1,l,i-1); if(val[i]*n<val[i]*d+val[j]*n){ return val[i]*n; } else{ return val[i]*d+maxres(l,i-1); } } int main(){ cin>>n; for(int i=0;i<n;i++){ int a; cin>>a; val[i]=a; } val[n]=-MAX; init(0,0,n-1); cout<<maxres(0,n-1)<<endl; }
#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...