Submission #959083

#	Time	Username	Problem	Language	Result	Execution time	Memory
959083		anton	Group Photo (JOI21_ho_t3)	C++17	100 / 100	337 ms	196452 KiB

Main

#include<bits/stdc++.h>

using namespace std;
#define int long long
const int MAX_N = 5001;

int n;
int dp[MAX_N];
int vals[MAX_N];
int pos[MAX_N];
int oc_under_pref[MAX_N][MAX_N];

void precalc(){
    for(int i = 0; i<=n; i++){
        vector<int> oc(n, 0);
        for(int j = 0; j<i; j++){
            oc[vals[j]]++;
        }
        int cur = 0;
        for(int j=0; j<=n; j++){
            oc_under_pref[i][j] = cur;
            if(j<n){
                cur += oc[j];
            }
        }
    }
}

int find_dp(){
    dp[0] = 0;
    for(int i = 0; i<n; i++){
        int cur_c= 0;
        for(int j = i; j<n; j++){
            //cout<<"j "<<j<<" "<<pos[j]<<" "<<oc_under_pref[pos[j]][j]<<endl;
            cur_c += pos[j]-oc_under_pref[pos[j]][i];
            cur_c-= (oc_under_pref[n][j]-oc_under_pref[n][i]-oc_under_pref[pos[j]][j]+oc_under_pref[pos[j]][i]);
            dp[j+1] =min(dp[j+1], dp[i]+cur_c);
        }
    }
    return dp[n];
}


signed main(){
    cin>>n;
    for(int i = 0; i<n; i++){
        cin>>vals[i];
        vals[i]--;
        pos[vals[i]] = i;
    }
    for(int i = 0; i<=n; i++){
        dp[i] = 1e18;
    }

    precalc();
    cout<<find_dp()<<endl;
}

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