Submission #521960

#TimeUsernameProblemLanguageResultExecution timeMemory
521960DanerZeinDischarging (NOI20_discharging)C++14
11 / 100
532 ms21148 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)); } int dp[MAX_N]; ll maxres(int l,int r){ if(dp[r]!=-1) return dp[r]; int i=query(0,0,n-1,0,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--){ int j=query(0,0,n-1,0,k); ans=min(ans,val[i]*d+maxres(0,k)); d++; } return dp[r]=ans; } int main(){ memset(dp,-1,sizeof dp); 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; }

Compilation message (stderr)

Discharging.cpp: In function 'll maxres(int, int)':
Discharging.cpp:46:9: warning: unused variable 'j' [-Wunused-variable]
   46 |     int j=query(0,0,n-1,0,k);
      |         ^
#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...