Submission #1016398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016398		Hanksburger	Group Photo (JOI21_ho_t3)	C++17	100 / 100	138 ms	98668 KiB

Main

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

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