Submission #1016397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016397		Hanksburger	Group Photo (JOI21_ho_t3)	C++17	100 / 100	137 ms	98640 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int x[5005][5005], a[5005], b[5005], dp[5005];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for (int i=1; i<=n; i++)
    {
        cin >> a[i];
        b[a[i]]=i;
    }
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            x[i][j]=x[i-1][j]+(j>=b[i]);
    for (int i=1; i<=n; i++)
    {
        dp[i]=1e9;
        int s=0;
        for (int j=i; j; j--)
        {
            s+=x[i][n]-x[i][b[j]]-x[j][n]+x[j][b[j]]+x[n][b[j]]-x[i][b[j]];
            dp[i]=min(dp[i], dp[j-1]+s);
        }
    }
    cout << dp[n];
}

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