Submission #856889

#TimeUsernameProblemLanguageResultExecution timeMemory
856889StefanSebezGroup Photo (JOI21_ho_t3)C++14
100 / 100
876 ms856 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N=5050; const int inf=1e17; int n,T[N]; int a[N],ind[N],dp[N]; void Update(int i,int qval){ while(i<=n){ T[i]+=qval; i+=i&(-i); } } int Get(int i){ int sum=0; while(i>=1){ sum+=T[i]; i-=i&(-i); } return sum; } /*int lc[2*N],rc[2*N],sum[2*N],nc,root; void Update(int &c,int ss,int se,int qind,int qval){ if(!c) c=++nc; if(ss==se) {sum[c]=qval;return;} int mid=(ss+se)/2; if(qind<=mid) Update(lc[c],ss,mid,qind,qval); else Update(rc[c],mid+1,se,qind,qval); sum[c]=sum[lc[c]]+sum[rc[c]]; } int Get(int c,int ss,int se,int qs,int qe){ if(se<ss) return 0; if(qs<=ss && se<=qe) return sum[c]; else if(qe<ss || se<qs) return 0; int mid=(ss+se)/2; return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe); }*/ signed main() { cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; ind[a[i]]=i; } for(int i=1;i<=n;i++) dp[i]=inf; dp[n+1]=0; for(int i=n;i>=1;i--){ int s=0,b[n+1]={0}; for(int j=i;j<=n;j++) Update(ind[j],1); for(int j=i;j<=n;j++) b[j]=Get(ind[j])-1; for(int j=i;j<=n;j++) Update(ind[j],-1); for(int j=i;j<=n;j++){ int k=ind[j],x=Get(n)-Get(k-1); s-=x; s+=b[j]; dp[i]=min(dp[i],dp[j+1]+s); Update(k,1); } for(int j=i;j<=n;j++) Update(ind[j],-1); /*for(int j=i;j<=n;j++) Update(root,1,n,ind[j],1); for(int j=i;j<=n;j++) b[j]=Get(root,1,n,1,ind[j])-1; for(int j=i;j<=n;j++) Update(root,1,n,ind[j],0); for(int j=i;j<=n;j++){ int k=ind[j],x=Get(root,1,n,k,n); s-=x; s+=b[j]; dp[i]=min(dp[i],dp[j+1]+s); Update(root,1,n,k,1); } for(int j=i;j<=n;j++) Update(root,1,n,ind[j],0);*/ } cout<<dp[1]<<endl; return 0; }
#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...