Submission #390640

#	Time	Username	Problem	Language	Result	Execution time	Memory
390640		wildturtle	Group Photo (JOI21_ho_t3)	C++14	100 / 100	740 ms	313412 KiB

Main

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,i,e,f,g,n,m,k,l;
ll A[5003],B[5003],C[5003][5003],D[5003][5003],dp[5003];
int main() {
    cin>>n;
    for(ll i=1;i<=n;i++) {
        cin>>A[i];
        B[A[i]]=i;
        dp[i]=1e18;
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=n;j>=1;j--) {
            C[i][j]=C[i][j+1];
            if(B[j]<B[i]) C[i][j]++;
        }
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=i;j<=n;j++) {
            D[i][j]=C[j][i]+D[i][j-1]-((j-1)-i+1-(C[j][i]-C[j][j+1]));
        }
    }
    for(ll i=1;i<=n;i++) {
        for(ll j=i-1;j>=0;j--) {
            dp[i]=min(dp[i],dp[j]+D[j+1][i]);
        }
    }
    cout<<dp[n];
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36