제출 #1165167

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165167		cpismylifeOwO	Group Photo (JOI21_ho_t3)	C++20	100 / 100	287 ms	98464 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long mod = 1e9 + 7;
const int MaxN = 5e3 + 5;

int n;
int arr[MaxN];

void Inp()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> arr[x];
    }
}

int rev[MaxN];
int Pre[MaxN][MaxN];
long long F[MaxN];

void Exc()
{
    for (int x = 1; x <= n; x++)
    {
        rev[arr[x]] = x;
    }
    for (int x = 1; x <= n; x++)
    {
        for (int y = 1; y <= n; y++)
        {
            Pre[x][y] = Pre[x][y - 1] + (rev[y] < rev[x]);
        }
    }
    F[n + 1] = 0;
    for (int x = n; x > 0; x--)
    {
        F[x] = 1e18;
        long long cur = 0;
        for (int y = x; y <= n; y++)
        {
            cur += Pre[y][n] - Pre[y][x - 1];
            cur -= (y - x) - (Pre[y][y] - Pre[y][x - 1]);
            F[x] = min(F[x], F[y + 1] + cur);
        }
    }
    cout << F[1];
}

int main()
{
    //freopen("A.INP", "r", stdin);
    //freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int test = 1;
    //cin >> test;
    for (int x = 1; x <= test; x++)
    {
        Inp();
        Exc();
    }
    return 0;
}

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