Submission #1236066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236066		iamhereforfun	Group Photo (JOI21_ho_t3)	C++20	100 / 100	80 ms	328 KiB

Main

// IamHereForFun //

#include <bits/stdc++.h>

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 5e3 + 5;
const int M = 2e5 + 5;
const int L = 12;
const int LG = 25;
const int P = 37;
const long long INF = 1e18 + 5;
const int MOD = 1e9 + 7;
const int nx[] = {0, -1, 0, 1}, ny[] = {-1, 0, 1, 0};

// dp[i] = minimum swap to fix the first i number.
// so we can't calculate the sum of positions to find it .-.z
// val[i] is the number of number that is smaller than i and appears after i
// we see that every time we push a number to the front, we can reduce some swap from the numbers that is smaller than it that has been swapped(basically the pos and val thingy)

int n, a[N], dp[N], val[N], pos[N];

void solve()
{
    cin >> n;
    for (int x = 1; x <= n; x++)
    {
        cin >> a[x];
        dp[x] = 1e9;
    }
    for (int x = 1; x <= n; x++)
    {
        for (int y = x; y <= n; y++)
        {
            if (a[y] < a[x])
                val[a[x]]++;
        }
    }
    dp[0] = 0;
    for (int x = 0; x < n; x++)
    {
        int cur = 0, id = 0;
        for(int y = 1; y <= n; y++)
        {
            if(a[y] > x)
            {
                pos[a[y]] = id;
                id++;
            }
        }
        for (int y = x + 1; y <= n; y++)
        {
            cur -= val[y];
            cur += pos[y];
            dp[y] = min(dp[y], dp[x] + cur);
            // cout << cur << " ";
        }
        // cout << "\n";
        // cout << dp[x] << " " << x << "\n";
        for (int y = 1; y <= n; y++)
        {
            if (a[y] == x + 1)
                break;
            if (a[y] > x + 1)
                val[a[y]]--;
        }
    }
    cout << dp[n];
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}

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