Submission #380859

#TimeUsernameProblemLanguageResultExecution timeMemory
380859Bill_00Group Photo (JOI21_ho_t3)C++14
100 / 100
508 ms165484 KiB
#include <bits/stdc++.h> #define ll long long #define N 5002 #define INF 1000000000 using namespace std; int a[N],dp[N],pos[N]; int p[N][N],x[N][N]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for(int i=1;i<=n;i++){ cin >> a[i]; pos[a[i]]=i; } for(int i=1;i<=n;i++){ for(int j=n;j>=1;j--){ if(a[j]<=i){ x[i][j]=x[i][j+1]+1; } else x[i][j]=x[i][j+1]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=(n-i+1);j++){ int pp=pos[i+j-1]; int u=x[i-1][pp]; p[i][j]=p[i][j-1]+pp+u-i-(x[i+j-1][pp+1]-x[i-1][pp]); } } for(int i=1;i<=n;i++){ dp[i]=INF; } for(int i=1;i<=n;i++){ for(int j=0;j<i;j++){ dp[i]=min(dp[j]+p[j+1][i-j],dp[i]); } } cout << dp[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...