Submission #1038888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038888		Otalp	Group Photo (JOI21_ho_t3)	C++14	100 / 100	250 ms	98344 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second

int a[5001];
int cnt[5001][5001];
int dp[5001];
int ddp[5001];
int pos[200100];


void solve(){
    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=1; j<=n; j++){
            cnt[i][j] = cnt[i-1][j] + (a[i] >= j ?1 :0);
        }
    }
    for(int i=1; i<=n; i++){
        int sum = 0;
        dp[i] = 1e9;
        for(int j=i; j>=1; j--){
            sum += cnt[pos[j]-1][i+1];
            sum += (cnt[n][j] - cnt[n][i+1]) - (cnt[pos[j]][j] - cnt[pos[j]][i+1]);
            dp[i] = min(dp[i], sum + dp[j-1]);
        }
        //cout<<dp[i]<<' ';
    }
    cout<<dp[n];

            


}

signed main(){
    solve();
}

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