Submission #936540

#TimeUsernameProblemLanguageResultExecution timeMemory
936540WongChun1234Group Photo (JOI21_ho_t3)C++14
100 / 100
589 ms792 KiB
#include<bits/stdc++.h> using namespace std; const int N=5050; int n,a[N],bit[2][N],pos[N],las[N][N],curr,dp[N]; void upd(int b,int id){ for (;id<N;id+=id&-id) bit[b][id]++; } int qry(int b,int id){ int ret=0; for (;id;id-=id&-id) ret+=bit[b][id]; return ret; } int main(){ cin>>n; for (int i=1;i<=n;i++){ cin>>a[i]; pos[a[i]]=i; } dp[0]=0; for (int i=1;i<=n;i++){ for (int j=0;j<=n;j++) bit[0][j]=bit[1][j]=0; dp[i]=INT_MAX; for (int j=n;j>i;j--) upd(0,pos[j]); curr=0; for (int j=i;j;j--){ curr+=qry(0,pos[j])+qry(1,n-pos[j]+1); dp[i]=min(dp[i],dp[j-1]+curr); //cout<<j<<"->"<<i<<" "<<curr<<"\n"; upd(1,n-pos[j]+1); } //cout<<i<<": "<<dp[i]<<"\n"; } cout<<dp[n]<<"\n"; }
#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...